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[N1][N1]来表示邻接矩阵并直接作为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。自环距离为0dist[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无法到达顶点3dist[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。通过这些测试可以全面检查算法的连通性判断、最值比较和边界处理是否正确。在你自己编写时务必用这些案例测试一下这是调试和确保代码鲁棒性的好习惯。