洛谷P2910详解：Floyd全源最短路与按顺序累加套路-北京尧图网络

1. 读懂题目救奶牛不是走一条路是按清单走完全程在洛谷的 USACO 题单里翻到 P2910第一眼是被这个名字唬住的Clear And Present Danger。这个短语在英语里有典故法学院教材里它是明显而现实的危险的判例标准《惊天核网》的英文原名也用的它。搁在这道题里其实就是约翰船长要开着船穿越海盗出没的水域去救他那头牛朋友。题目本身倒没名字那么吓人N 最大 100K 最大 10000是一道很典型的图论入门题。不过我把题意反复读了三遍才意识到它并不是普通的最短路——它给了一张危险度海图还给了你必须依次拜访的岛屿顺序。也就是说你没法挑一条最顺的路从头走到尾而是要像完成任务清单一样一站一站把路径拼出来。这道题适合三类人看刚学完 Floyd 想找题练手的同学在洛谷上刷 USACO 题单但被题意绕晕的选手以及想搞明白为什么这题用 Floyd 而不用 Dijkstra的进阶新手。下面我把完整思路、两种代码实现、和我提交过程中踩过的坑全部捋一遍保证你能直接照着复现。1.1 背景故事和输入输出题目背景是这样的约翰有一头奶牛被困在了某个海域他需要按照海图从 1 号岛出发依次经过若干个岛屿最终到达目标岛。海图上给了一个 N×N 的矩阵第 i 行第 j 列的数字表示从岛 i 到岛 j 的危险系数数字越大越危险。约翰希望走一条总危险系数最小的路线。注意这里的用词它不是传统的给出若干条边的图而是直接给了一个稠密矩阵任意两个岛之间都有直接的航线。换句话说这是一个完全图只不过每条边的权值都写在矩阵里了。输入格式分两块第一行两个整数 N 和 KN 是岛屿数量K 是约翰必须经过的岛屿数量。接下来 N 行每行 N 个数是危险系数矩阵。接下来一行或 K 个数是约翰要依次拜访的岛屿编号 F1, F2, ..., Fk。注意题目并没有让你把这 K 个点重新排序顺序是强制的。输出只有一行最小总危险系数。这里有一个关键点很多初学者第一次做会忽略矩阵里给的是直接从 i 到 j的危险度但实际航行时你完全可以选择绕路。比如从岛 1 到岛 3 的危险度是 100但你可以先到岛 2危险度 10再从岛 2 到岛 3危险度 20那实际值就是 30 而不是 100。所以这背后的模型是标准的最短路问题不是简单的矩阵加和。1.2 样例推演为什么它不是传统最短路看一个最小化的例子你就明白了。假设 N3矩阵长这样0 5 100 5 0 20 100 20 0K2旅行顺序是 1 3。如果你只看矩阵直接从 1 到 3 要花 100。但显然最优路线是 1 → 2 → 3总代价 5 20 25。这就是为什么不能直接输出矩阵里对应的那几个格子。你得先算出全源最短路也就是任意两点之间的最小代价然后再按顺序把相邻两个必经点之间的距离累加起来。这个先求全源最短路再顺序累加的思路就是整道题的灵魂。2. 为什么这题的正解绕不开 Floyd2.1 一个看起来很自然的替代方案跑 K 次单源最短路很多人第一反应是既然要从 F1 走到 F2从 F2 走到 F3……那不就是以每个 F 为起点跑一次单源最短路吗这个思路没有错但你要算一笔账。以朴素 Dijkstra 为例单次复杂度是 O(N²)。N100 时单次就是 10000 次操作。K 最大 10000那么总操作量大约 1×10^8 次。这个量级在 C 里其实勉强能跑但在 Java 里就可能吃紧而且代码复杂度比 Floyd 高不少。如果用堆优化的 Dijkstra单次是 O((NM)logN)。这是一个完全图MN²10000所以单次大约 10^5 次操作K 次下来就是 1.4×10^9 的操作量这就有点悬了。而 Floyd 呢三重循环 O(N³) 100³ 1,000,000也就是一百万次操作。加上最后顺序累加的 K10000 次总操作量大约 101 万次。这个量级对任何语言来说都是秒过。方案复杂度N100, K10000 时的操作量评价Floyd 顺序累加O(N³ K)约 1.01×10^6极稳代码短朴素 Dijkstra × KO(K × N²)约 1×10^8勉强代码长堆优化 Dijkstra × KO(K × (NM)logN)约 1.4×10^9不推荐2.2 Floyd 在这里的三个不可替代优势首先是代码量优势。Floyd 的核心就三重循环加起来不到十行。在竞赛里代码越短意味着出错概率越低。USACO 这种老牌比赛很多选手都不是不会算法而是死在实现细节上Floyd 能把这类风险压到最低。其次是完全图适配。Floyd 不需要建邻接表直接用矩阵算输入矩阵恰好就是它的天然数据结构。你甚至不需要额外做任何转换读入完直接开跑。第三是查询 O(1)。Floyd 跑完之后得到的是任意两点之间的最短路所以你之后无论要查多少段都是 O(1) 查表。哪怕 K 从 10000 变成 1000000这一步也完全不是瓶颈。2.3 Floyd 的循环顺序一个老生常谈但致命的细节Floyd 的标准写法是三层循环中转点 k 必须放在最外层for (int k 1; k n; k) for (int i 1; i n; i) for (int j 1; j n; j) d[i][j] min(d[i][j], d[i][k] d[k][j]);为什么 k 在最外层因为这本质上是一个动态规划d[i][j] 表示只允许经过前 k 个中转点时从 i 到 j 的最短路。每多一个中转点 k就尝试用 k 来松弛一次所有点对。如果你把 i 放外层那就是只用中转点 i 去松弛某些点对状态转移的递推关系就乱了算出来大概率是错的。这里顺便呼应一下搜索词里那个洛谷动态规划题单——Floyd 在 DP 视角下就是从只经过 0 个中转点一直递推到经过全部 N 个中转点理解了这一点循环顺序就再也不会写错。3. 能过题的代码C 与 Java 双版本实现3.1 C 实现和读入细节直接上完整代码我加了注释#include bits/stdc.h using namespace std; const int MAXN 105; const int MAXK 10005; int d[MAXN][MAXN]; // 危险系数矩阵同时也是最短路结果 int route[MAXK]; // 约翰必须经过的岛屿顺序 int main() { ios::sync_with_stdio(false); cin.tie(0); int n, k; cin n k; // 直接读入矩阵因为题目保证任意两个岛之间都有航线 // 所以不需要初始化 INF读入的就是初始距离 for (int i 1; i n; i) { for (int j 1; j n; j) { cin d[i][j]; } } for (int i 1; i k; i) { cin route[i]; } // Floyd 求全源最短路 for (int mid 1; mid n; mid) { for (int i 1; i n; i) { for (int j 1; j n; j) { if (d[i][mid] d[mid][j] d[i][j]) { d[i][j] d[i][mid] d[mid][j]; } } } } // 按顺序累加相邻必经点之间的最短路 long long ans 0; for (int i 1; i k; i) { ans d[route[i]][route[i 1]]; } cout ans \n; return 0; }注意几个细节数组下标从 1 开始方便直接对应输入的岛屿编号省去减一操作减少出错概率。route数组要开到 K5不是 K1因为你是从 1 开始存到 K 的。ios::sync_with_stdio(false)和cin.tie(0)建议写上虽然这题数据量不大但养成习惯没坏处。3.2 Java 实现与 Scanner 的注意点很多在洛谷上用 Java 的同学最担心的就是读入速度。这题 N×N 矩阵加 K 个路线数字总共最多 100×100 10000 20000 个数用 Scanner 完全够了。不过我还是给一个稍微稳一点的写法import java.util.*; public class Main { public static void main(String[] args) { Scanner sc new Scanner(System.in); int n sc.nextInt(); int k 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(); } } int[] route new int[k 1]; for (int i 1; i k; i) { route[i] sc.nextInt(); } for (int mid 1; mid n; mid) { for (int i 1; i n; i) { for (int j 1; j n; j) { d[i][j] Math.min(d[i][j], d[i][mid] d[mid][j]); } } } long ans 0; for (int i 1; i k; i) { ans d[route[i]][route[i 1]]; } System.out.println(ans); sc.close(); } }这里有个 Java 特有的小坑Math.min只对int做基本数学判断不会溢出因为中间结果d[i][mid] d[mid][j]是在int范围内比较的。危险系数最大 1000N 最大 100最坏情况一条路径也不超过 1000×100 100000离 int 上限远得很。所以完全不用担心溢出问题。3.3 数据类型选择int 够用但我为什么用 long long我们来算一下极端情况。每个危险系数最大 1000一条路径上最多经过多少个点从 F1 到 F2 的最短路在最坏情况下可能绕很多个中转点理论上一条简单路径最多经过 N 个点也就是最多 100 个点权值不超过 100000。乘上 K-1 段最多 9999 段总答案上限大约是 10 亿恰好压在 int 的边界附近。用long long是为了彻底规避风险。尤其是当你想把这个模板拿去处理更大数据时比如危险系数是 10^9int 必然溢出。在自己的代码里养成凡是累加未知上限的变量默认用 long long的习惯能帮你省掉很多隐蔽的 WA。4. 提交记录里翻出来的几个坑4.1 把点编号直接当数组下标用导致查表错位这是我见过最多人犯的错。题目输入的岛屿编号是 1 到 N但很多同学习惯了 0-indexed建数组的时候用的是d[n][n]然后读入时用d[i-1][j-1]存最后累加时又写成了d[route[i]][route[i1]]。一旦 route 里的数大于等于 n就直接数组越界程序崩掉或者返回一个奇怪的值。解决办法很粗暴要么全程 1-indexed要么全程 0-indexed绝不混用。我个人推荐 1-indexed因为可以完全照抄题目的编号逻辑少一步脑筋急转弯。4.2 INF 设多大才算安全这题因为读入的是完全矩阵所以不需要初始化 INF。但如果以后做到类似但可能缺边的题目比如矩阵里某些位置是 0 表示不可达你就必须初始化 INF。很多人的习惯是memset(d, 0x3f, sizeof(d))然后用0x3f3f3f3f表示无穷大。为什么是0x3f3f3f3f因为它等于 1061109567两个这样的数相加约 21 亿依然小于 int 的上限 2147483647不会溢出变成负数导致松弛判断出问题。当然本题因为任意两点都可达你完全可以不初始化 INF直接把读入矩阵当成初始状态跑 Floyd。这也是我在代码里没有初始化 INF 的原因——少做一步就少一个出错点。4.3 样例过了却 WA顺序累加时的边界问题我当年交这题第一次 WA就是栽在这个地方route 数组存到下标 K但循环写成了for (int i 0; i k; i)然后访问route[i]和route[i1]。因为 route[0] 没有赋值默认是 0第一段就成了从岛 0 走到 route[1]答案莫名其妙多了一段。正确写法是for (int i 1; i k; i) { ans d[route[i]][route[i 1]]; }因为你需要累加的是 (F1,F2), (F2,F3), ..., (F_{k-1},F_k)一共 k-1 段。下标从 1 到 k-1正好覆盖全部相邻配对。4.4 自造数据的验证方法如果你提交前不确定自己的 Floyd 写得对不对最简单的验证方法就是手算一个 N3 的小数据。比如3 2 0 2 10 2 0 3 10 3 0 1 3一眼看出 1 到 3 的直接代价是 10但 1→2→3 是 235所以答案应该是 5。跑一遍代码如果输出不是 5那肯定是 Floyd 写崩了。更严格一点可以写一个对拍程序用小规模的 N比如 4用 Floyd 的结果和一个暴力的做法比如对每个起点跑朴素 Dijkstra对比。两边输出一致基本就稳了。对拍是竞赛里最实用的工具比反复肉眼检查代码高效得多。5. 从 P2910 看 USACO 最短路题的套路5.1 必经点顺序问题 vs 旅行商问题的本质区别刷题多了你会发现USACO 喜欢把简单模型套上花哨的故事。P2910 的故事是救奶牛模型是按给定顺序访问 K 个点的最小路径代价。这里面最容易混淆的是它和旅行商问题TSP看起来有点像都有多个必经点但本质完全不同。TSP 给的是一组点顺序不限每个点恰好访问一次找最短环路。那是 NP 问题N 稍微大一点就只能状态压缩 DP。而 P2910 的顺序是固定的你要做的只是把头尾相邻的点两两配对每一对之间求一次最短路最后加在一起。顺序一旦固定组合爆炸就消失了问题变成一个多项式时间就能解决的最短路拼接问题。你一定要记住这个判断标准如果必经点顺序可以随意排列那是 TSP别想贪心如果顺序已经给定那每一段都是独立的直接拼最短路边即可。5.2 为什么逐段最短路之和就是全局最优这背后其实有一个看似显然但值得仔细想一想的性质。假设顺序是 A → B → C我们把路径分成 A 到 B 和 B 到 C 两段。如果我们选了一条 A 到 C 的路径它本身当然也经过 B但它中间的那段经过 B 的迂回不一定等于从 B 出发的最短路。关键在于每一段的代价是可以独立最小化的。A 到 B 怎么走完全不会影响 B 到 C 的走法因为它们之间只共享一个端点 B。所以全局最小代价 A 到 B 的最短路 B 到 C 的最短路。你可以用反证法想如果存在一条全局路径其中 A 到 B 那段不是最短路那么把这一段替换成 A 到 B 的最短路总代价只会更小而且不会破坏经过 A、B、C这个约束。所以贪心地逐段取最短路结果就是全局最优。这个性质在 K 很大的时候特别有用。你甚至可以先把路线里的相邻点对去重如果某个点对重复出现直接乘以出现次数省下来的累加时间虽然不多但思路很清楚地说明了每一段互相独立这个事实。5.3 这题的变体方向什么时候 Floyd 会失效既然 P2910 的 N 只有 100Floyd 毫无争议。但题目稍加改变就要重新选算法了。假设 N 变成 5000K 变成 100000Floyd 的 O(N³) 直接爆炸这时候你必须退回到对每个必经点跑一次 Dijkstra的思路。因为单源最短路的复杂度是 O((NM)logN)在这个规模下反而更划算。再比如如果矩阵不是稠密的而是稀疏图给出的是 M 条边而不是 N² 个矩阵值那 Floyd 的 N³ 就更不划算了。这种时候就要先读清数据范围再决定算法。USACO 和洛谷上的题数据范围本身就是解题提示的一部分——看到 N100往 Floyd 想看到 N10^5赶紧把邻接表、堆优化 Dijkstra 拿出来。我在实际做题里的习惯是先看 N 和 K 的上限再决定算法。这个顺序比先读题目背景重要得多。题目背景只是包装数据范围才是真实的出题人意图。回到 P2910——这道题放在 USACO 2008 年的 Open 场里级别不高难度也温和但它把全源最短路预处理顺序累加查询这个组合练得很透彻。Floyd 本身并不难写真正难的是读题后准确判断要算全源最短路这个念头。把这个套路存进脑子里以后再遇到必须按顺序经过一批点求最小总代价的题你就能第一时间反应过来了。

洛谷P2910详解：Floyd全源最短路与按顺序累加套路

相关推荐

刚刚，又一个“剪视频的”冲进 GitHub 日榜：AutoClip 到底做了什么让开发者集体 star

ThinkPHP动态页面404排查：宝塔8.5+Nginx环境实战修复

Ansible -i 参数全解：主机清单与动态 Inventory 实战指南

更多资讯

编程尚未被解决：复杂度管理才是真正的挑战

FlyEnv本地开发环境：按需启动省内存，多版本切换告别环境折磨

基于知识图谱的古诗词问答系统：本科毕设从图谱构建到问答源码全流程

C++手写DFA词法分析器与LALR(1)语法分析器实战

BIOS、电源选项与简介：整机调优的三大核心要素

CoreCoder源码精读系列：逐文件拆解agent.py、llm.py、context.py，看懂生产级Agent的每个设计决策

今日更新

再见，SSE！你好，Streamable HTTP！轻松开发 Streamable HTTP MCP Server 并接入 TaoToken

工业软件标准化路线图：国产替代的落地施工图

VCMI安卓版实操指南：原生运行英雄无敌3的3步技术落地

本周精选

CMOS设计三大物理效应：体效应、沟道长度调制与亚阈值导电

微信小程序在线阅读毕设全解析：Java后端+MySQL+避坑实战

Android音频问题五层分析法：从App到Codec的系统化诊断

本月热门

我发现了一个新思路：用 Remotion + Claude Code 像写代码一样自动化生成短视频

Windows下 Codex 中 Chrome 和 Computer Use 插件不可用问题排查及解决参考方式：TaoToken 统一 Key 配置与验证

2026 大模型集体涨价：用 Python 做企业 Token 成本测算与选型避坑（附配置）

读完文章，想聊聊您的网站？