洛谷P2910这道题老玩家应该都不陌生USACO 2008 Open的银组题题面包装成一个航海冒险故事Farmer John带着奶牛去寻宝要在N个岛屿之间按指定顺序航行每条航线有一个“危险度”你要找出一条总危险度最小的航线序列。剥掉这层故事外衣它其实是一道非常经典的全源最短路多次查询题目也是我眼中最适合用来搞懂Floyd-Warshall算法的入门题。我第一次做这道题的时候刚学完最短路满脑子都是Dijkstra结果一看数据范围N≤100、M≤10000立刻意识到每段航程单独跑一次单源最短路虽然也能过但Floyd预处理一次、之后每个点对O(1)查询才是更优雅、更贴合题目本质的做法。这篇就围绕P2910把Floyd的前因后果、代码实现、易错细节一次讲透后面再聊几个同类题给想系统刷图论的朋友一条清晰的进阶路线。1. 题目到底在问什么从冒险故事到图论模型1.1 剥掉故事外壳剩下什么原题的输入格式是第一行两个整数N和MN是岛屿数M是FJ必须经过的岛屿数量。接下来是一个N×N的矩阵第i行第j列表示从岛屿i到岛屿j这条航线的危险度。最后M行或同一行用空格隔开给出M个岛屿编号FJ从1号岛出发必须按这个顺序依次经过这些岛问最小总危险度是多少。看到这你可能会想这不就是把给定的相邻岛屿之间的距离加起来吗不对关键陷阱在于——图上任意两点之间不一定直飞最便宜。比如从岛A到岛C直达可能要10但先绕到岛B只要347那聪明人肯定选择绕路。所以你需要知道的是任意两个岛屿之间的“最短危险度”这就是全源最短路。更准确地说这题的模型是给定一个有向带权图多次询问若干点对之间的最短路然后把它们累加起来。注意题目只要求“依次经过”这些点没有要求经过所有点也没有要求回到起点。读到这里你就该有一个条件反射如果查询次数很多图节点数又不大Floyd是首选。1.2 多次查询场景下的算法选择有人可能会问我也可以用N次Dijkstra啊N100堆优化跑N遍最坏也就100×100×log100照样轻松过关。这个说法没毛病但做题不能只看“能不能过”还要看“哪个思路更接近题眼”。给你算笔账Floyd的时间复杂度是O(N^3)N100时是10^6次运算一次预处理之后任意两个点之间的距离都可以从表里直接取复杂度O(1)。后续M最多10000次查询总复杂度约10^610^4非常舒服。而如果每段航程都单独跑一次DijkstraM10000时就是10000×100×log100虽然N小也扛得住但代码明显更啰嗦还要维护优先队列。更重要的是Floyd在编写上极其简单一个三重循环十几行就能写完不容易出错非常适合作为USACO铜组升银组、或者初学者刚接触图论时的第一道“全源最短路”例题。1.3 数据范围与答案精度题目限制N≤100M≤10000。矩阵里的危险度是整数理论上每条边最大可能到几千但M上万次累加后答案有可能超过int的安全范围吗说实话大部分测试数据int能过但竞技编程的肌肉记忆告诉我凡是求和就用long或者long long。反正Java的long、C的long long都是64位存这点累加结果绰绰有余别因为省这点空间导致溢出WA得不偿失。2. Floyd的核心思想与三个高频易错点2.1 三重循环的顺序为什么不能改Floyd的代码看起来简单但很多新手第一次写都是照着模板抄抄完也不知道为什么k在最外层。我来把原理讲透。用动态规划的眼光看定义f[k][i][j]表示“只允许使用前k个点作为中间点时从i到j的最短路长度”。初始状态f[0][i][j]就是直接边的权值。状态转移方程是f[k][i][j] min(f[k-1][i][j], f[k-1][i][k] f[k-1][k][j])意思很直白要么不经过第k个点最短路仍然是用前k-1个点中转得到的要么经过第k个点那就把路径拆成i到k、k到j两段两段都只允许用前k-1个点中转。因为i到k和k到j本身不会再用k作为中转点否则就是重复绕圈最短路不会出现正权环所以这个拆法是完备的。把这个三维数组压成二维滚动数组k这一维被迭代覆盖就变成了我们熟悉的d[i][j] min(d[i][j], d[i][k] d[k][j])注意k是“阶段”不是普通的循环变量。如果把k放到最内层就相当于在某个中间点集合还没完整建立的时候就去更新其他路径状态就乱了。具体表现是小数据可能碰巧算出正确答案数据一复杂就WA。所以以后不管在哪看到Floyd的模板外层一定是k这个顺序是算法的灵魂不能动。2.2 初始化、INF与溢出Floyd的初始化根据题目给的图不同有两种写法。P2910比较友好N×N矩阵直接给全对角线上也是0所以你甚至不用额外初始化读进来直接跑三重循环就行。但很多最短路模板题给的图不是完全图有边的地方给权值没边的地方需要你自己设成无穷大INF。这时候有两个坑要提醒你对角线d[i][i]必须初始化为0否则自环不为0会导致后续更新出奇怪结果。INF不能设成Integer.MAX_VALUE因为代码里会做d[i][k] d[k][j]两个大数相加直接溢出变成负数反而可能把最短路“更新”成一个错误的负数。稳妥做法是设INF 0x3f3f3f3fC里约等于10^9或者设成1000000007这种明显大于所有可能路径和的值。如果还是担心可以在更新前加一句判断如果d[i][k]或d[k][j]是INF就跳过。这道题不需要这么麻烦但换到别的题你就知道这个坑有多疼。2.3 下标问题1-index还是0-indexP2910的岛屿编号从1开始所以很多C选手习惯把数组开到int d[105][105]循环范围1到N读到的编号直接当作数组下标用非常自然。但如果你用Python或者习惯0-index读入的每个编号都要-1再作为下标。这个操作看起来无关紧要却是最容易出错的细节。我见过有人矩阵读成0-index路径编号却没减1结果访问数组越界或者累加时路径完全错位。我的建议是写代码之前先想清楚自己的下标体系是几开头然后全程保持一致。题目给的是几开头就用几开头省得每处都要换算反而容易漏。3. 三种参考代码与关键步骤解读3.1 Java版先读矩阵再Floyd边读路径边累加这是我推荐的最优写法逻辑上干净利落import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc new Scanner(System.in); int n sc.nextInt(); int m sc.nextInt(); int[][] d new int[n 1][n 1]; for (int i 1; i n; i) { for (int j 1; j n; j) { d[i][j] sc.nextInt(); } } // Floyd-Warshallk是允许经过的中间点集合的“规模” for (int k 1; k n; k) { for (int i 1; i n; i) { for (int j 1; j n; j) { if (d[i][k] d[k][j] d[i][j]) { d[i][j] d[i][k] d[k][j]; } } } } long ans 0; int cur 1; // 从1号岛出发 for (int i 1; i m; i) { int nxt sc.nextInt(); ans d[cur][nxt]; cur nxt; } System.out.println(ans); sc.close(); } }这段代码的核心妙处在于矩阵读完之后Floyd立刻执行。此时M个路径编号还没读进内存但这完全不影响因为Floyd只需要图的邻接矩阵不需要知道查询序列。等到最短路表算好再开始逐个读编号、累加答案程序逻辑和输入顺序天然契合还省了一个存路径的数组。有人可能会有疑问输入顺序明明是“先矩阵后M个编号”我在读编号之前跑Floyd会不会导致输入流里还有数据没读而卡住不会。Scanner或cin读的是缓冲区里的数据你晚点读它也还在那里输入顺序和计算顺序可以不完全一致只要每个数据最终被正确读取就行。3.2 C版适合比赛现场的简洁写法C版本的思路完全一致代码更短我比赛时通常这样写#include bits/stdc.h using namespace std; int n, m; int d[105][105]; int main() { cin n m; for (int i 1; i n; i) { for (int j 1; j n; j) { cin d[i][j]; } } for (int k 1; k n; k) { for (int i 1; i n; i) { for (int j 1; j n; j) { if (d[i][k] d[k][j] d[i][j]) { d[i][j] d[i][k] d[k][j]; } } } } long long ans 0; int cur 1; for (int i 1; i m; i) { int nxt; cin nxt; ans d[cur][nxt]; cur nxt; } cout ans endl; return 0; }注意两点数组开到105而不是100防止d[100][100]越界答案变量用long long。这两条是我吃过亏之后养成的习惯写进模板里就不会忘。3.3 Python版注意输入方式Python刷题最怕的就是输入慢。N才100矩阵最多10000个数直接input()读还能接受但M上万的时候逐行input()会有一定开销。稳妥方案是用sys.stdin.buffer.read()一次性把整个输入读完再按空格切分import sys def main(): data sys.stdin.buffer.read().split() it iter(data) n int(next(it)) m int(next(it)) d [[0] * n for _ in range(n)] for i in range(n): for j in range(n): d[i][j] int(next(it)) for k in range(n): for i in range(n): for j in range(n): if d[i][k] d[k][j] d[i][j]: d[i][j] d[i][k] d[k][j] ans 0 cur 0 # 岛屿编号减1 for _ in range(m): nxt int(next(it)) - 1 ans d[cur][nxt] cur nxt print(ans) if __name__ __main__: main()Python的三重循环是10^6次本地跑起来完全没压力。唯一的提醒是0-index后所有编号记得-1包括起点cur也要从0开始。这是我每次写Python版图论题都要在脑子里过一遍的坎。4. 提交记录里的踩坑实录4.1 输入顺序错乱这道题的输入顺序相当有迷惑性文件名里带“Clear And Present Danger”题面又是大段故事很多人读题不仔细以为第二行就是M个路径编号。结果矩阵还没读完就开始处理路径后面全乱了。正确的顺序是第一行N和M→N行矩阵→M个编号。我自己第一次提交时就是因为想着“反正都是数字”读入逻辑写成了先读M个编号再读矩阵样例直接读歪。排查方法很简单把读进来的前几个数打印出来对照样例输入哪里错了一目了然。4.2 漏掉从1号点出发的那一段这个坑比较隐蔽。题目说FJ从1号岛出发要依次经过给定的M个岛。但有些人累加时会这样写ans 0; for (int i 1; i m; i) { ans d[path[i]][path[i 1]]; // 下标处理不当 }或者更常见的错误是直接用第一个给定的编号作为起点从头开始累加完全忽略了从1号岛到第一个编号岛屿之间还有一段路程。如果第一个给定编号不是1答案就会偏小。我自己的习惯就是代码里先写一句int cur 1;每次读到一个新编号就累加d[cur][nxt]再把cur更新成这个编号。这样永远不会漏段逻辑也直观。4.3 数组越界和编号处理如果你用的是1-index数组开成[100][100]当n100索引从1到100时d[100][100]是合法的但如果你不小心访问了d[101][...]就会RE。所以我一般直接开105多一些余量没坏处。如果你把数组开成[n][n]的0-index而路径编号又没减1那就会访问到d[100][...]导致越界。这种RE只在特定数据下触发特别难查。我的经验是遇到数组越界先检查所有下标是不是都从0开始且所有从外部读入的编号都做了-1处理。4.4 Floyd跑完发现答案比预期大有一种情况会让你怀疑人生Floyd写对了输入也读对了但答案就是比预想的大。这时检查一下你是不是把d[i][j]初始化为无穷大了然后更新时又没有加特判导致d[i][k] d[k][j]溢出。还有一种情况你用了int存路径但单个危险度可能超过2^31-1加法溢出后变成负数但Floyd里的if判断又被更新成奇怪的值。所以这道题虽然常用int矩阵累加建议用long。矩阵本身用int没问题因为单条边权不会大得离谱。5. 从P2910延伸开去Floyd还能做什么5.1 灾后重建动态加点洛谷P1119“灾后重建”是同一个Floyd思想换了个包装村庄在地震后按时间顺序修复每次某个村庄修复后所有和最短路相关的查询就要更新一次。这题的解法就是按时间顺序枚举k刚好对应Floyd外层循环的“阶段”概念。如果你理解了P2910里k为什么在外层再去做P1119会特别顺畅因为那题里k就是“修复时间顺序”算法和题意完美嵌合。这两题一起刷Floyd的DP内核基本就拿捏了。5.2 传递闭包与最小环Floyd不只是求最短距离它还能处理一类叫“传递闭包”的问题典型题是P2419“Cow Contest”。那题要判断N头奶牛之间的胜负关系能否确定排名本质上是用Floyd式的逻辑判断更新“i能否赢j”。另一个经典应用是最小环。在无向带权图中用Floyd求最小环的套路是外层k枚举最大编号的点内层i、j枚举两个已有点先查d[i][j]和边i-k、k-j能不能构成一个环再正常更新最短路。这个思路也是“枚举阶段”的延伸学完之后你的图论工具箱会多好几件武器。5.3 什么时候不用FloydFloyd好写但不是万能药。它的复杂度O(N^3)决定了N超过500左右就会吃力。N10^5的图你要全源最短路得跑Johnson算法或者直接N次Dijkstra如果只是单源最短路肯定选Dijkstra或SPFA。我的经验是看到“多次询问任意两点之间最短路”且N比较小时优先Floyd看到“单起点到所有点”时直接Dijkstra看到“有负权边且无负环”时Bellman-Ford或SPFA。选对算法比会背模板重要得多。6. 刷题心得与建议P2910这道题我每年给新人推荐的时候都会强调一遍它最值钱的地方不是让你学会抄Floyd模板而是让你理解“预处理查询”这个思维模式。很多图论题看起来是在模拟一条路径实际考的是先建全源最短路表再对每个询问O(1)查表拼答案。你把这个模式记在脑子里以后再碰到类似“按顺序经过若干关键点”的题第一反应就不会是傻乎乎地每段跑Dijkstra了。另外刷洛谷的时候我建议把这道题归入自己的“图论入门”题单里和P1119、P2419、P6175放在一起连着做。你会发现它们的内核高度统一都是Floyd那一层“阶段”循环在变着花样考你。如果能顺手把三种语言的版本各写一遍对下标转换和输入处理的熟练度也会有明显提升。最后分享一个我自己的小习惯写Floyd之前先在注释里把那句话写出来——“k是允许经过的中间点编号的最大值”。每次写循环前念一遍就不会再把k放错位置。这个习惯帮我省下过无数次调试时间希望你也能用得上。