1. 题目解析与核心需求拆解
“哈利·波特的考试”这道题，是很多C语言学习者和算法初学者在练习数据结构（尤其是图论）时，会遇到的一道经典题目。我第一次看到这个标题时，也以为会有什么魔法咒语或者复杂的剧情逻辑，但实际上，它考察的是一个非常纯粹的图论算法问题——多源最短路径。题目背景通常是这样：霍格沃茨有N门魔法课，每门课可以看作一个顶点，课程之间的转换难度（或者说是“魔法值”）构成了带权有向图的边。哈利·波特需要找到一门“最难”的课，这里的“最难”不是指课程本身内容，而是指从这门课出发，到其他所有课程中，最难到达的那门课所需要的“魔法值”最大。听起来有点绕？别急，我们换个说法。
这本质上是一个单源最短路问题的集合。对于每一门课（即每一个顶点），我们都需要计算它到其他所有顶点的最短距离。然后，对于这门课，我们找出这些最短距离中的最大值（即从这门课出发，到最难到达的课程的距离）。最后，我们比较所有课程的这些“最难到达距离”，找出其中最小的那个，以及对应的课程。如果存在多门课满足条件，则输出编号最小的。如果存在某门课无法到达其他所有课（即图不连通），则输出0。
所以，核心算法需求非常明确：
- 建立图模型：将课程和转换难度建模为带权有向图。
- 计算任意两点间最短路径：这是算法的核心。由于需要计算所有顶点对之间的最短路径，使用 Floyd-Warshall 算法是最直接的选择。它的时间复杂度是 O(N³)，对于题目常见的 N ≤ 100 的数据范围是完全可行的。
- 后处理与结果判定：对每个顶点 i，找出
dist[i][1...N]中的最大值maxDist[i]（即从i出发到其他点的最远距离）。然后，在所有maxDist[i]中找出最小值minOfMaxDist。如果某个maxDist[i]为无穷大（表示有不可达的顶点），则整体结果无效。
理解了需求，我们再来看看实现中的几个关键点，这也是新手最容易栽跟头的地方。
2. 图的数据结构与Floyd算法实现精讲
2.1 邻接矩阵的初始化：无穷大与自环
在C语言中，我们通常用一个二维数组dist[N+1][N+1]来表示邻接矩阵，并直接作为Floyd算法的距离矩阵。初始化是第一步，也是决定算法正确性的基石。
#define MAX_V 105 // 假设最大顶点数，略大于题目范围 #define INF 0x3f3f3f3f // 一个常用的“无穷大”值 int dist[MAX_V][MAX_V]; int N, M; // N顶点数，M边数 void initGraph() { // 1. 自己到自己的距离为0 for (int i = 1; i <= N; i++) { for (int j = 1; j <= N; j++) { if (i == j) { dist[i][j] = 0; } else { dist[i][j] = INF; // 初始化为无穷大，表示不可达 } } } // 2. 读入边信息 // 假设输入格式为：顶点a, 顶点b, 权值w for (int k = 0; k < M; k++) { int a, b, w; scanf("%d %d %d", &a, &b, &w); dist[a][b] = w; // 有向图 // 如果题目是无向图，则需要加上 dist[b][a] = w; } }这里有几个极易出错的细节：
INF的选择：为什么是0x3f3f3f3f？这个值约等于10^9，在int范围内，且两个这样的值相加不会溢出（0x3f3f3f3f * 2 < 0x7fffffff）。如果你用INT_MAX或0x7fffffff，在松弛操作dist[i][k] + dist[k][j]时，一旦dist[i][k]为最大值，相加就会导致整数溢出，变成负数，从而影响算法结果。0x3f3f3f3f是一个安全且方便 memset 初始化的值（memset(dist, 0x3f, sizeof(dist))会将所有字节设为0x3f，对于int数组，每个int就变成了0x3f3f3f3f）。- 自环距离为0：
dist[i][i] = 0必须显式设置。这是Floyd算法正确工作的前提，表示从自己到自己的最短距离是0。虽然逻辑上显而易见，但忘记初始化会导致后续判断出错。 - 重边处理：题目通常会说“题目保证输入数据是有效的”，但有些题目可能存在重边（即同一对顶点有多条边）。这时需要取最小值
dist[a][b] = min(dist[a][b], w)。养成这个习惯能避免很多隐蔽的bug。
2.2 Floyd-Warshall算法的三重循环：顺序与逻辑
Floyd算法的核心代码非常简短，但内涵深刻。
void floyd() { for (int k = 1; k <= N; k++) { // 中间点 for (int i = 1; i <= N; i++) { for (int j = 1; j <= N; j++) { // 关键：防止INF相加溢出，必须先判断 if (dist[i][k] < INF && dist[k][j] < INF) { if (dist[i][j] > dist[i][k] + dist[k][j]) { dist[i][j] = dist[i][k] + dist[k][j]; } } } } } }为什么k循环必须放在最外层？这是理解Floyd算法的关键。算法的思想是动态规划：dist[k][i][j]表示只允许使用前k个顶点作为中间点，从i到j的最短路径长度。当k从1遍历到N时，我们逐渐放宽“可使用的中间点”的范围，最终得到任意两点间的最短路径。将状态压缩到二维数组后，就要求k这层循环必须在外层，以保证在计算dist[i][j]时，dist[i][k]和dist[k][j]已经是考虑了前k-1个中间点的最优解。如果顺序错了，结果就不正确。
关于INF的判断：这是实现中的另一个关键点。如果dist[i][k]或dist[k][j]是INF，那么它们的和是无意义的，直接比较可能会因为INF被定义为一个具体的大数而产生错误更新。因此，必须先判断两者都不是INF，再进行松弛操作。有些简单的实现省略了这个判断，在INF选择得当且题目数据保证不会出现INF+某值的情况下可能也能通过，但加上判断是更严谨、更安全的做法。
3. 结果计算与边界条件处理
Floyd算法跑完后，dist矩阵就存储了所有点对之间的最短距离。接下来就需要根据题目要求，找出哈利·波特应该参加的那门考试（课程）。
int findExamCourse() { int minOfMaxDist = INF; // 记录所有“最难距离”中的最小值 int examCourse = 0; // 对应的课程编号 for (int i = 1; i <= N; i++) { int maxDistForI = 0; // 从课程i出发，到其他课程的最远最短距离 // 遍历所有其他课程j for (int j = 1; j <= N; j++) { if (dist[i][j] > maxDistForI) { maxDistForI = dist[i][j]; } } // 关键判断：如果从i出发，存在不可达的课程，则maxDistForI会是INF if (maxDistForI == INF) { // 这门课无法作为起点，因为它不能到达所有其他课 // 根据题目要求，一旦出现这种情况，整个结果就是0 // 但我们需要遍历完所有课程确认吗？其实找到第一个就可以返回0了。 // 更严谨的做法：记录下这个情况，但继续循环，因为题目要求输出编号最小的可行课程。 // 实际上，如果有一门课不可达，那么“所有最难距离中的最小值”这个集合就不完整，最终结果应为0。 // 我们可以在循环外用一个标志位记录。 } // 如果这门课可以到达所有其他课，则用它的最难距离去更新全局最小值 if (maxDistForI < minOfMaxDist) { minOfMaxDist = maxDistForI; examCourse = i; } } // 后处理：检查是否所有课程都能作为起点（即图是强连通的？不，题目要求是每个顶点都能到其他所有顶点，这是“竞赛图”的连通性？） // 实际上，题目要求的是：如果存在至少一门课，从它出发可以到达其他所有课，那么就在这些课里找“最难距离”最小的。 // 如果不存在这样的课（即对于每个顶点i，都存在另一个顶点j使得dist[i][j]==INF），则输出0。 // 更准确的判断逻辑： int canFind = 0; int globalMinMax = INF; int ansId = 0; for (int i = 1; i <= N; i++) { int maxDist = -1; int isConnected = 1; // 假设i能到所有点 for (int j = 1; j <= N; j++) { if (dist[i][j] > maxDist) { maxDist = dist[i][j]; } if (dist[i][j] == INF) { isConnected = 0; // i无法到达j break; // 已经确定i无效，内层循环可以提前结束 } } if (isConnected) { // i可以到达所有顶点 canFind = 1; if (maxDist < globalMinMax) { globalMinMax = maxDist; ansId = i; } } } if (canFind) { // 输出 ansId 和 globalMinMax printf("%d %d\n", ansId, globalMinMax); } else { printf("0\n"); } return 0; }这部分代码的逻辑比看起来要复杂，主要体现在连通性判断上。题目真正的意思是：在那些能够到达其他所有顶点的顶点中，找一个“最难距离”（即到其他点的最短距离的最大值）最小的。如果不存在这样的顶点（即对于图中每一个顶点，至少存在一个它无法到达的顶点），则输出0。
常见的错误理解：
- 认为需要整个图是强连通图（任意两点互相可达）。其实不需要，只需要存在一个顶点，它能到达其他所有点即可。这个顶点就像是一个“源点”。
- 在计算
maxDistForI时，如果遇到INF，不能简单地将其当作一个巨大值参与比较。因为INF意味着不可达，这门课本身就应该被排除在候选之外。所以必须在计算maxDistForI的过程中，一旦发现INF，就标记该顶点无效。 - 输出要求：如果找到，输出编号最小的那个课程及其对应的“最难距离”。所以我们在更新
globalMinMax时，判断条件是maxDist < globalMinMax，而不是<=。这样当距离相等时，不会更新ansId，从而保证了编号小的优先（因为我们是按编号从小到大遍历的）。
4. 完整代码实现与测试用例分析
将以上所有部分组合起来，并加上输入输出，就得到了完整的解决方案。下面是一个整合后的代码框架，并附上详细的注释。
#include <stdio.h> #include <string.h> #define MAX_V 105 #define INF 0x3f3f3f3f int dist[MAX_V][MAX_V]; int N, M; void initGraph() { // 使用memset初始化所有距离为INF，非常高效 memset(dist, 0x3f, sizeof(dist)); for (int i = 1; i <= N; i++) { dist[i][i] = 0; // 自环为0 } for (int i = 0; i < M; i++) { int a, b, w; scanf("%d %d %d", &a, &b, &w); // 处理可能的重复边，取最小值 if (w < dist[a][b]) { dist[a][b] = w; } } } void floyd() { for (int k = 1; k <= N; k++) { for (int i = 1; i <= N; i++) { // 一个小优化：如果i到k不可达，则跳过对j的循环 if (dist[i][k] == INF) continue; for (int j = 1; j <= N; j++) { // 防止INF相加溢出 if (dist[k][j] == INF) continue; int newDist = dist[i][k] + dist[k][j]; if (dist[i][j] > newDist) { dist[i][j] = newDist; } } } } } int main() { scanf("%d %d", &N, &M); initGraph(); floyd(); int candidateId = 0; int globalMinMaxDist = INF; // 遍历每一门课，寻找符合条件的“源点” for (int i = 1; i <= N; i++) { int maxDist = -1; int isValid = 1; // 标记顶点i是否可达所有其他顶点 for (int j = 1; j <= N; j++) { if (dist[i][j] > maxDist) { maxDist = dist[i][j]; } // 如果发现不可达的点，则顶点i无效 if (dist[i][j] == INF) { isValid = 0; break; // 提前结束内层循环 } } // 如果顶点i有效，且它的“最难距离”是目前最小的 if (isValid && maxDist < globalMinMaxDist) { globalMinMaxDist = maxDist; candidateId = i; } } if (candidateId == 0) { // 没有找到任何一个顶点能到达所有其他顶点 printf("0\n"); } else { printf("%d %d\n", candidateId, globalMinMaxDist); } return 0; }现在，我们来设计几个测试用例，验证代码的正确性。
测试用例1：基础连通案例
输入： 6 11 3 4 70 1 2 1 5 4 50 2 6 50 5 6 60 1 3 70 4 6 60 3 6 80 5 1 100 2 4 60 5 2 80（这是一个经典测试图，需要手动计算或信任已知结果）预期输出应该是2 60。顶点2到其他点的最短距离最大值是60（到顶点4），在所有顶点中这个值最小。
测试用例2：存在不可达顶点
输入： 3 2 1 2 10 2 3 20顶点1无法到达顶点3（dist[1][3] = INF）。顶点2可以到达1和3。顶点3无法到达1。因此，只有顶点2是有效的“源点”。它的maxDist是max(20, 0) = 20（到顶点3的距离是20，到自己的距离是0）。输出应为2 20。
测试用例3：全不连通
输入： 4 0没有边。对于任何一个顶点i，到其他任意j (j!=i)的距离都是INF。因此，不存在有效的“源点”。输出应为0。
测试用例4：多个候选，取编号最小
输入： 4 3 1 2 5 1 3 5 1 4 5只有顶点1可以到达2、3、4。顶点2、3、4都无法到达其他非自身的顶点。所以唯一有效的是顶点1，它的maxDist是5。输出1 5。如果图是对称的（无向边），那么每个顶点都能到达其他点，且maxDist都相等，此时应输出编号最小的顶点1。
通过这些测试，可以全面检查算法的连通性判断、最值比较和边界处理是否正确。在你自己编写时，务必用这些案例测试一下，这是调试和确保代码鲁棒性的好习惯。
