洛谷P2910这道题，老玩家应该都不陌生，USACO 2008 Open的银组题，题面包装成一个航海冒险故事：Farmer John带着奶牛去寻宝，要在N个岛屿之间按指定顺序航行，每条航线有一个“危险度”，你要找出一条总危险度最小的航线序列。剥掉这层故事外衣，它其实是一道非常经典的全源最短路+多次查询题目，也是我眼中最适合用来搞懂Floyd-Warshall算法的入门题。

我第一次做这道题的时候，刚学完最短路，满脑子都是Dijkstra，结果一看数据范围N≤100、M≤10000，立刻意识到每段航程单独跑一次单源最短路虽然也能过，但Floyd预处理一次、之后每个点对O(1)查询才是更优雅、更贴合题目本质的做法。这篇就围绕P2910把Floyd的前因后果、代码实现、易错细节一次讲透，后面再聊几个同类题，给想系统刷图论的朋友一条清晰的进阶路线。

1. 题目到底在问什么：从冒险故事到图论模型

1.1 剥掉故事外壳，剩下什么

原题的输入格式是：第一行两个整数N和M，N是岛屿数，M是FJ必须经过的岛屿数量。接下来是一个N×N的矩阵，第i行第j列表示从岛屿i到岛屿j这条航线的危险度。最后M行（或同一行用空格隔开）给出M个岛屿编号，FJ从1号岛出发，必须按这个顺序依次经过这些岛，问最小总危险度是多少。

看到这你可能会想：这不就是把给定的相邻岛屿之间的距离加起来吗？不对，关键陷阱在于——图上任意两点之间不一定直飞最便宜。比如从岛A到岛C，直达可能要10，但先绕到岛B只要3+4=7，那聪明人肯定选择绕路。所以你需要知道的是任意两个岛屿之间的“最短危险度”，这就是全源最短路。

更准确地说，这题的模型是：给定一个有向带权图，多次询问若干点对之间的最短路，然后把它们累加起来。注意题目只要求“依次经过”这些点，没有要求经过所有点，也没有要求回到起点。读到这里你就该有一个条件反射：如果查询次数很多，图节点数又不大，Floyd是首选。

1.2 多次查询场景下的算法选择

有人可能会问：我也可以用N次Dijkstra啊，N=100，堆优化跑N遍最坏也就100×100×log100，照样轻松过关。这个说法没毛病，但做题不能只看“能不能过”，还要看“哪个思路更接近题眼”。

给你算笔账：Floyd的时间复杂度是O(N^3)，N=100时是10^6次运算，一次预处理之后，任意两个点之间的距离都可以从表里直接取，复杂度O(1)。后续M最多10000次查询，总复杂度约10^6+10^4，非常舒服。而如果每段航程都单独跑一次Dijkstra，M=10000时就是10000×100×log100，虽然N小也扛得住，但代码明显更啰嗦，还要维护优先队列。

更重要的是，Floyd在编写上极其简单，一个三重循环十几行就能写完，不容易出错，非常适合作为USACO铜组升银组、或者初学者刚接触图论时的第一道“全源最短路”例题。

1.3 数据范围与答案精度

题目限制N≤100，M≤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 = 0x3f3f3f3f（C++里约等于10^9），或者设成1000000007这种明显大于所有可能路径和的值。如果还是担心，可以在更新前加一句判断：如果d[i][k]或d[k][j]是INF就跳过。这道题不需要这么麻烦，但换到别的题你就知道这个坑有多疼。

2.3 下标问题：1-index还是0-index

P2910的岛屿编号从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-Warshall：k是允许经过的中间点集合的“规模” 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]，当n=100，索引从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 什么时候不用Floyd

Floyd好写，但不是万能药。它的复杂度O(N^3)决定了N超过500左右就会吃力。N=10^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放错位置。这个习惯帮我省下过无数次调试时间，希望你也能用得上。