刷最短路题单见过最多的一种场景是嘴上说着“我会Dijkstra”一打开题发现根本不是让你求最短距离而是求最长路、求能不能到、求所有点的可达数量。我记得有一份老题单标题写在洛谷题号后面就是“图论题解——最短路”但里面五道题P1567、P2951、P1807、P2419、P4306每一道的算法都不一样线性DP、BFS、拓扑排序、Floyd传递闭包、bitset优化。这恰好是初学者最容易混淆、又最值得串起来理解的五个方向。如果你刚学完最短路基础正想在“最短路周边”刷一组题建立体系感这五道题是很好的样本。1. 先看题单五个题号五种最短路变体这套题单的价值不在题量而在它把“图上路径问题”拆成了好几个层次。很多人以为最短路就是Dijkstra一把梭其实真正的竞赛题里最短路经常以三种面孔出现求最短、求最长、求可达性。P1567属于典型“看着像DP其实可以建模成图”P2951是真正的单源无权最短路P1807则是把最短路反过来求最长路P2419和P4306都是Floyd的亲戚一个是传递闭包一个是bitset加速全源连通。1.1 题单速览题号一句话理解核心算法主要难点P1567求最长连续升温天数线性递推 / 隐式DAG最长链把序列问题抽象成图问题P2951找离1号点最远的点BFS无权图最短距离的分层性质P1807求DAG上1到n的最长路拓扑排序 DP区分最短与最长、不可达处理P2419判断有多少头牛排名可确定Floyd传递闭包关系闭包的建模P4306统计有向图所有可达点对数bitset优化传递闭包复杂度优化和bitset细节这五道题合在一起刚好覆盖了最短路专题里最常用的三把钥匙BFS处理无权图、拓扑序处理DAG、Floyd处理全源关系。它们之间还有清晰的前后依赖关系你只有先理解“路径长度可以重新定义”才能接受P1807求最长路你只有先理解Floyd的三层循环才能接受P2419和P4306本质上是在做一个“bool版Floyd”。1.2 为什么P1567会出现在“最短路”题单里P1567这题本身没有任何图的输入输出题目就是给你n天的气温让你统计气温连续上升的最长天数。看到这里你可能会疑惑这不是一道模拟/DP题吗怎么混进最短路题单了这就是这题放最前面的用意。所有最短路算法本质上都在解决一个问题在一个由节点和边组成的图里沿着某种转移关系走到某个状态的最优“距离”。P1567里的节点可以理解为“第i天处在升温序列中”的状态唯一的转移是如果第i1天气温比第i天高就允许从i连一条有向边到i1边权为1。那么题目要的“最长连续升温天数”就是这张隐式图上的最长链长度。把这个思路想明白之后你就建立了“最短路/最长路不一定要真的读一张图”的直觉。以后看到看似是序列DP的题也可以想想能不能用图论视角重新描述这对后面理解DAG最长链非常有帮助。1.3 刷题顺序安排我的建议是按照P1567 → P2951 → P1807 → P2419 → P4306的顺序刷。理由很简单P1567帮你热身最短路建模P2951是纯粹的BFS没有任何“最长”干扰适合复习队列分层扩展P1807在BFS基础上引入DAG和边权把思维扭到“最长”方向P2419把算法从单源扩展成全源开始接触关系的闭包运算P4306则是P2419的复杂度升级版逼你想到bitset。2. P1567从连续升温到隐式图上的最长链2.1 题干到底在问什么P1567是一件“反套路”的事情它问的不是“最短”而是“最长连续满足条件的天数”。朴素做法很简单从左往右扫维护一个当前连续长度cur当a[i] a[i-1]时cur自增否则cur重置为1每一步更新答案ans。核心递推式是这样的#include bits/stdc.h using namespace std; int main() { int n; scanf(%d, n); int x, last 0, cur 1, ans 1; for (int i 1; i n; i) { scanf(%d, x); if (i 1) { if (x last) cur; else cur 1; ans max(ans, cur); } last x; } printf(%d\n, ans); return 0; }这里有个小坑很多新手会把cur初始化为0然后遇到a[i] a[i-1]就加1到最后发现单元素区间时答案是0。正确做法是让cur最少为1因为单独一天气温也算连续上升段。如果第n 1答案是1不是0。2.2 用图论视角重新看它既然这是最短路题单我们就不能只停在递推。把a[i]看成图的节点如果a[i1] a[i]就定义一条从i指向i1的有向边边权为1。题目求的就是这张图中最长的“路径”长度。因为边永远从低索引指向高索引这张图不存在环是一张DAG。所以“最长连续升温天数”本质上就是DAG上的最长链。这个视角似乎多此一举但对后面的影响很大。P1807要解决的长路问题就是在一个真正输入邻接表和边权的DAG上做同样的事情把“满足某种比较关系的连续状态”替换成“从u到v的转移边”把“累计天数”替换成“累计边权”问题就泛化成了“求图上最长路径”。这就是为什么刷题时强调抽象能力你看到的不是一道DP题而是图论题的化身。2.3 这道题给后续刷题的启发P1567真正教会我们的事情是不要被“距离”两个字限制住。最短路的“距离”可以是路径条数可以是边权和可以是经过的点数可以是“升温天数”甚至可以是某种关系是否成立。这个思维转换在P1807、P2419、P4306里会被反复用到——P1807要求距离就是边权和P2419把“路径”变成“胜负关系的传递”P4306把“路径”变成“是否连通”。所以刷这题的时候别只满足于AC试着在脑海里把序列转换成图你会发现后面几题不会产生“这也能叫最短路”的排斥感。3. P2951无权图上用BFS找最远躲藏点3.1 BFS为什么可以求无权最短路P2951是USACO的Hide and Seek。题意是有n个点m条无向边牛从谷仓1号点出发要找一个离谷仓最远的点躲起来如果距离相同就取编号最小的那个。边没有权值或者说每条边权值都是1这种情况不需要Dijkstra用BFS就够了。BFS的核心性质是在无权图中队列元素是按“到源点距离”分层入队的。第一次访问到某个点v时得到的dis[v]一定是最短距离。因为BFS是从近到远一层一层扩展先访问到的层数不可能大于后访问到的层数。这个性质在带权图里并不成立只有在所有权重都为1或者权值只有0和1用双端队列时才成立。所以P2951的正确算法顺序是BFS求出dis数组然后遍历所有节点找出dis最大且编号最小的点。#include bits/stdc.h using namespace std; const int MAXN 20005; vectorint g[MAXN]; int dis[MAXN]; int main() { int n, m; scanf(%d%d, n, m); for (int i 0; i m; i) { int u, v; scanf(%d%d, u, v); g[u].push_back(v); g[v].push_back(u); } memset(dis, -1, sizeof(dis)); queueint q; dis[1] 0; q.push(1); while (!q.empty()) { int u q.front(); q.pop(); for (int v : g[u]) { if (dis[v] -1) { dis[v] dis[u] 1; q.push(v); } } } int pos 1; for (int i 1; i n; i) if (dis[i] dis[pos]) pos i; int cnt 0; for (int i 1; i n; i) if (dis[i] dis[pos]) cnt; printf(%d %d %d\n, pos, dis[pos], cnt); return 0; }3.2 代码里的三个细节第一个细节是dis初始化成-1而不是0。dis[1] 0其他点没访问到就是-1这样既能当访问标记又能区分“不可达”和“距离为0”。如果你初始化成0就分不清哪些点是起点本身、哪些点是距离全是0的未访问点。第二个细节是输出时要统计“距离最远的点有多少个”。原题输出三部分躲藏点编号、最远距离、以及最远距离的点的个数。很多人只写了编号和距离丢掉了个数这种题最容易因为输出格式不全被扣分。第三个细节是无向边存两遍。我见过不少人对每个u、v只push了一次然后样例居然过了因为样例图恰好是对称的这种侥幸在数据稍大时就原形毕露。建图是否双向是这类题的常见失分点。3.3 BFS与Dijkstra的边界感P2951不需要Dijkstra但你需要知道什么时候不能只用BFS。如果这题的边有权值比如距离是1、2、3BFS的分层性质就失效了因为某条长边的点可能比短边的点更早进入队列但它的真实距离更大。只有边权全部相同或为0/1时才优先考虑BFS或者0-1 BFS。具体来说0-1 BFS就是当边权只有0和1时用deque存储节点0边从队头入队1边从队尾入队维持队列单调性。P2951显然满足“全为1”所以普通BFS就够。你要在脑里建一张决策表无权图用BFS非负权图用Dijkstra有负权/判负环用SPFA或Bellman-FordDAG用拓扑序。这题就是帮你把第一行“无权图”钉死。4. P1807DAG上的最长路拓扑排序DP4.1 为什么DAG是特殊结构P1807题意是n个点m条有向边每条边有权值保证图是有向无环图求1号点到n号点的最长路径长度不存在输出-1。这里的“最长路”不是让我们把Dijkstra改成求max因为Dijkstra的贪心依赖的是“当前距离最小的点永远不会被更小值更新”换成“距离最大”之后这个贪心性质就没了。你无法保证当前最大距离的点以后不会被更大的值更新。DAG的特殊之处在于无环所以可以拓扑排序。拓扑序保证每条边的起点u一定在终点v之前被处理。这意味着当处理到u时所有能从起点1到达u的路径信息都已经计算完毕可以安全地用dp[u]去更新dp[v]。这种无后效性的顺序就是动态规划所需要的。所以DAG上的最长路不需要用堆不需要跑SPFA只需拓扑排序过程中一路做“模仿松弛”的DP。4.2 完整实现流程算法流程分四步建图时记录每条边的终点和权值并统计每个点的入度。所有入度为0的点入队开始拓扑排序。出队时遍历该点的所有出边尝试更新dp[终点] max(dp[终点], dp[当前点] 边权)。每处理一条边就把终点的入度减1。如果某个终点的入度变成0将它入队。核心代码长这样#include bits/stdc.h using namespace std; const int INF 0x3f3f3f3f; const int MAXN 1505; struct Edge { int to, w; }; vectorEdge g[MAXN]; int indeg[MAXN]; int dp[MAXN]; int main() { int n, m; scanf(%d%d, n, m); for (int i 0; i m; i) { int u, v, w; scanf(%d%d%d, u, v, w); g[u].push_back({v, w}); indeg[v]; } fill(dp 1, dp n 1, -INF); queueint q; for (int i 1; i n; i) if (indeg[i] 0) q.push(i); dp[1] 0; // 起点到自己距离为0 while (!q.empty()) { int u q.front(); q.pop(); for (Edge e : g[u]) { if (dp[u] ! -INF) { dp[e.to] max(dp[e.to], dp[u] e.w); } indeg[e.to]--; if (indeg[e.to] 0) q.push(e.to); } } printf(%d\n, dp[n] -INF ? -1 : dp[n]); return 0; }4.3 边界情况处理最常见的错误是初始化和不可达判断不一致。dp数组必须初始化成负无穷常用的标记是-0x3f3f3f3f不要用0。因为如果起点到某点真的存在一条负权路径用0初始化会干扰判断。虽然这道题的边权看起来都是非负但最好按“可能有负权”的习惯去写这样以后遇到负权DAG也能直接套。第二个边界是起点1可能不在拓扑序的开头。拓扑排序会把所有入度为0的点都入队包括那些和起点无关的点。这没关系只要保证只有dp[u]不是负无穷时才做更新即可。如果某个点和起点不连通它的dp会一直保持负无穷永远不会去更新后面的点。第三个容易出错的地方是入度的处理和DP更新要在同一个循环里完成。你不能先跑一遍拓扑排序存下顺序再跑一遍DP除非你把出队的顺序记录在数组中。边数多的时候两种写法效率差不多但直接在拓扑过程中DP更省事也不需要额外数组。P1807的另一种解法是用SPFA求最长路因为DAG没有环SPFA不会陷入无限松弛。但SPFA的复杂度不够稳定而且SPFA本身的最坏情况是O(nm)在竞赛里并不让人放心。既然题目已经保证DAG用拓扑排序DP就是最优雅、最稳的做法它还能分出一条“学DAG DP”的主线。5. P2419和P4306传递闭包与bitset加速5.1 从Floyd到传递闭包P2419题意是Cow Contest有n头牛给出m对胜负关系a能赢b如果一头牛和其他n-1头牛之间的关系都能确定直接或间接那么它的排名就可以确定。问有多少头牛的排名可以被确定。这里不用真的求最短路但用的思路和Floyd完全一致。我们维护一个bool数组g[i][j]表示“i能赢j”。胜负关系有传递性如果i能赢kk能赢j那么i也能赢j。所以我们要对g做一次传递闭包把间接关系都补全。这本质上就是一个bool版Floydfor (int k 1; k n; k) for (int i 1; i n; i) for (int j 1; j n; j) if (g[i][k] g[k][j]) g[i][j] true;很多初学者会问为什么中间点k要放在最外层循环因为Floyd本质是按“允许经过前k个点”来扩张状态。当k1时只允许经过1号点当k2时允许经过1号点和2号点……如果把k放在内层就会出现刚更新的关系马上又参与同一层传递的混乱情况结果可能漏掉某些组合。记住k必须在最外层这是Floyd三连的全部秘密。5.2 P2419的判定核心完成传递闭包之后如何判断一头牛的排名已知对牛i来说它和另一头牛j的关系有两种i能赢j或者j能赢i。只要这两种情况至少成立一种就说明i和j之间谁强谁弱是确定的。统计所有j中满足这个条件的数量如果等于n-1说明i和所有牛的关系都已知排名就能确定。完整代码如下#include bits/stdc.h using namespace std; const int MAXN 105; bool g[MAXN][MAXN]; int main() { int n, m; scanf(%d%d, n, m); for (int i 0; i m; i) { int a, b; scanf(%d%d, a, b); g[a][b] true; } for (int k 1; k n; k) for (int i 1; i n; i) for (int j 1; j n; j) if (g[i][k] g[k][j]) g[i][j] true; int ans 0; for (int i 1; i n; i) { int known 0; for (int j 1; j n; j) { if (i ! j (g[i][j] || g[j][i])) known; } if (known n - 1) ans; } printf(%d\n, ans); return 0; }注意判断条件要写i ! j否则自己和自己会因为g[i][i]为true而多算一次导致known变成n答案出错。这是一个非常隐蔽的细节尤其你如果在读入时顺手把g[i][i]设成了true更要小心。5.3 P4306用bitset把n遍DFS压到常数倍P4306是[JSOI2010]连通数题意更直接给一张n个点的有向图用一个n×n的01矩阵表示边问图中有多少个点对(i, j)满足i能到达j通常包括i j。n的范围比较大朴素做法可以跑n次DFS或BFS每次从一个点出发统计可达点数复杂度O(n×(nm))当n达到2000甚至更高时这个开销会很紧张。P4306的正解是用bitset优化传递闭包。我们用bitset 类型的数组b[i]表示从点i出发能到达的所有点的集合。初始时b[i]的第i位设为1表示自己可达自己读入邻接矩阵时如果a[i][j]为1就把b[i]的第j位设为1。然后做和Floyd一样的枚举for (int k 0; k n; k) for (int i 0; i n; i) if (b[i][k]) b[i] | b[k];这段代码的语义是如果i能到k那么i就能到k能到的所有点。b[i] | b[k]一步就把k的所有可达点合并进i的可达集合。注意这里依然要先枚举k再枚举i这样才能保证传递性逐层扩散。最后统计所有b[i]中1的个数就是答案。完整代码#include bits/stdc.h using namespace std; const int MAXN 2005; vectorbitsetMAXN reach; int main() { int n; scanf(%d, n); reach.resize(n); char s[MAXN]; for (int i 0; i n; i) { scanf(%s, s); reach[i][i] 1; for (int j 0; j n; j) if (s[j] 1) reach[i][j] 1; } for (int k 0; k n; k) for (int i 0; i n; i) if (reach[i][k]) reach[i] | reach[k]; int ans 0; for (int i 0; i n; i) ans reach[i].count(); printf(%d\n, ans); return 0; }为什么bitset快因为C的bitset对位的或运算是按机器字长批量处理的一条指令能合并64位甚至更多。原来的bool数组Floyd循环里最内层是n次单点判断现在变成一次位运算常数大大缩小。复杂度从O(n^3)变成O(n^3 / 64)在n2000时完全轻松。实操中还有一个容易踩的坑如果自环在题面中不算连通数那统计答案时就先不设置reach[i][i] 1或者在最后减去n。很多题解默认连通点对包括自己P4306按这个写法直接统计即可。但如果换平台、换题目一定要看样例到底是包含自环还是不包含。我的习惯是先按包含自环写跑样例验证输出如果不匹配马上改成不含自环的重新统计。5.4 面向全源最短路再往外走一步P2419和P4306解决的都是“全源可达性”问题也就是说它们是最短路问题的一个简化版不求具体距离只问有没有路。如果要更进一步求真正意义上的全源最短路经典选择是Floyd或Johnson算法。Floyd适合顶点数在300以内的稠密图Johnson适合边数多但点也不算巨大的有负权图。它们和传递闭包的核心逻辑一样都要枚举中间点作为“关系传递”的桥梁只是维护的数据从bool变成了距离。所以刷过P2419、P4306之后再去看Johnson全源最短路会有一种“这条路我走过”的熟悉感。6. 防坑清单刷最短路题最容易翻车的几件事6.1 做题先问自己三句话我最想强调的习惯是拿到一道图论题在写代码前先问三句话——图是有向还是无向边权是否全相等图中有没有环这三个答案直接决定算法。P2951无向无权图BFSP1807有向并且保证无环拓扑DPP2419和P4306本质上是有向关系图的闭包Floyd或bitset。如果你不先回答这三问很容易跑偏比如在无权图里用Dijkstra或者在已经保证DAG的图里用SPFA都能AC但复杂度不稳定。6.2 初始化和不可达判断最短路题80%的细节错误都出在初始化。BFS用-1区分已访问和未访问Dijkstra用0x3f3f3f3f表示无穷DAG最长路用-INF表示不可达。这里的关键是一致性判断是否可达的条件必须和初始化值配套。P1807里我用dp[e.to] -INF判断“没有更新过”如果初始化成0那起点到负权边的终点时就会判断错误输出结果也会错。推荐大家统一把“不可达”和“距离为0”在脑中当成两种完全不同的状态。6.3 读入与存图很多图论题给出的点编号是1到n不是0到n-1。如果你习惯数组从0开始建图时一定要把全部下标减1并把所有循环范围改成0到n-1。我曾经在P2951里因为忘记把m条边的节点编号处理一致导致越界排查了很久。另外读入字符串的01矩阵时字符串s[j]是字符1不是数字1比较时要写成1。这种字符和数字的混淆在P4306里非常常见。有向图存边时要注意重边。在BFS和Dijkstra里重边没有太大影响但在拓扑排序和统计入度时每条重边都要对应一次入度增加。如果你用set去重反而可能弄巧成拙所以一般情况下邻接表存重边就够关键是入度统计不要漏。6.4 对拍和自查技巧刷这类题强烈建议写一个数据生成器去对拍。生成器可以很小n取8到15m随机取20到50权值随机自己写一个暴力的Floyd或DFS验证答案。对拍别贪大小数据反而更容易暴露问题。我的习惯是写三个文件gen.cpp生成随机数据brute.cpp暴力验证sol.cpp提交解法然后写个脚本循环跑几百组一旦输出不一致立刻打印那组数据人工检查。小技巧暴力代码越简单越好哪怕复杂度是O(n^3)都可以因为只在小数据上跑。这样能在几分钟内找出边界错误、初始化错误和入度统计错误比自己盯着代码看一个小时有效得多。最后说一点个人体会这五道题解出来之后最短路专题的地图基本就清晰了。单源无权找BFS单源非负找DijkstraDAG上随便跑DP全源关系找Floyd数据大了就上bitset。以后再遇到“最短路的变种”你不太会被题目表面的“最长”“连通”“排名”迷惑而是能一眼看出它到底是在求哪一类路径问题。这套思路比多刷十道同质化模板题都值。