最短路与状态建图

一、引入：为什么 BFS 会在带权图面前轰然倒塌？

在无权图的世界里，我们用最质朴的 BFS（广度优先搜索）就能横扫所有最短路问题：队列一层层向前推进，波纹一样荡开，谁先出队，谁的步数就铁定最少。

但现实竞赛中的图，往往充满了“权值”的博弈。想象这样一个极简场景：

从起点 $S$ 到终点 $T$，有两条路线：

1. 路线 A：直达航线，只需走 1 步，但票价高达 100 元；
2. 路线 B：转机路线，先花 1 元到中转城市 $A$，再花 1 元从 $A$ 到 $T$，总共走 2 步，花费只需 2 元。

如果直接套用普通 BFS，算法在第一层扫描时赫然看到直达航线“只用走 1 步”，就会立刻判定找到了“最优解”，直接把答案定格在 100 元！而真正便宜的“走 2 步花 2 元”的方案，因为步数更多，被死死挡在后面。

核心痛点：“步数最少”绝不等于“花费最少”。面对各异的边权，我们必须彻底打破“谁先到达谁最优”的直觉，重新认识图论中最核心的底层动作。

二、最短路的核心原子操作：“松弛”到底在干什么？

无论后面讲到的 Dijkstra、Bellman-Ford 还是 Floyd，它们的名字再响亮，本质上都在不知疲倦地重复同一个基本动作：松弛（Relaxation）。

1. 松弛的物理意义：给旧合同换一份更便宜的报价

我们手里握着一张表格 dis，记录着从源点 $s$ 到各个城市的“当前最低已知花费”。

• 刚开局时，起点到自己的花费是 dis[s] = 0；
• 其他所有未探索的节点，花费全部初始化为天文数字 INF（代表我们还没买到任何通往该节点的票）。

现在，我们眼前出现了一条从 $u$ 到 $v$、权值为 $w$ 的有向边。我们在心里打一下算盘：

如果是，那就立刻撕毁旧合同，把 dis[v] 刷新为更便宜的报价：

if (dis[u] != INF && dis[u] + w < dis[v]) {
    dis[v] = dis[u] + w;
}

这就是松弛。不要把这个词想得高深莫测，它就是极其朴素的商业逻辑：“旧报价太贵了，我发现了一条绕经 $u$ 更划算的路线，立刻更新底牌。”

2. 两个致命的边界死穴

1. INF 绝不能随便拿去加减：INF 只是我们标记“尚未可达”的哨兵，不是一笔真实的巨额路费。如果 dis[u] == INF，说明连 $u$ 自己都根本没走到，绝对不能拿 INF + w 去跟别人比，否则在 C++ 中很容易造成整数溢出，直接爆成负数，把整张表彻底带偏。
2. 零权边是真实存在的“免费通道”：权值为 0 代表通过这条边不需要花钱，绝不代表“不存在边”。如果你用邻接矩阵存图，习惯用 0 表示两点间没有边，就会亲手把所有的免费路线全部抹杀。

三、算法选型全景：不要拿着大炮打蚊子

面对一道最短路题目，第一步永远是审视边权的性质与查询的模式，而不是闭着眼睛敲模板：

⚠️ 教练提醒：

• 有向图 vs 无向图：绝不是算法选型的依据！无向图仅仅相当于“正反两条有向边”，Dijkstra 和 Floyd 处理有向图和无向图完全一视同仁。
• 最小生成树（MST）不是最短路：MST 追求的是“把所有点连通起来的总边权最小”；最短路追求的是“从固定起点走到特定终点的单条路径权值和最小”。二者目标完全不同，绝不能混用！

四、堆优化 Dijkstra：为什么最小的那个可以一锤定音？

Dijkstra 算法的灵魂在于贪心。它每一步都在做一件事：从所有尚未盖章确认的点中，挑选出当前 dis 最小的那个点 $u$，直接宣布：“到 $u$ 的最短距离已经敲定，后续绝不可能更短了！”

1. 贪心的物理依据：非负权边的铁壁防线

凭什么敢断定当前最小的不会被推翻？

假设当前未确定的点中，$u$ 的距离是 5，其他未确定的点距离都在 7、10、15…… 试想：有没有可能先绕到那个距离是 7 的点，再沿着后面的边绕回 $u$，反而跑出一个比 5 还小的花费？

绝对不可能！ 因为全图的边权都非负（$w \ge 0$）。从一个花费已经高达 7 的点出发，后面的路每走一步都在“往上加钱”，花费只会越来越大，怎么可能绕一圈反而降到 5 以下？

这就是 Dijkstra 贪心成立的前提：只要边权非负，当前距离最小的未确定点，就已经迎来了它的终局最优解。

2. 手推五条边：体会距离的刷新与沉淀

我们用一组经典有向边来模拟全程： 源点 $s = 1$。 边集：$1 \to 2$ (权 3)、$1 \to 3$ (权 6)、$2 \to 3$ (权 2)、$2 \to 4$ (权 4)、$3 \to 4$ (权 1)。

到点 3 的直达路线花 6 元，经过点 2 中转后被刷新为 5 元；到点 4 先拿到 7 元的报价，经过点 3 后再次刷新为 6 元。这就是松弛在实际运行中的层层递进。

3. 堆中的“幽灵记录”与懒惰删除

在上面第 2 步处理点 1 时，点 3 被赋予了报价 6，我们把 (6, 3) 扔进了优先队列； 但在第 3 步处理点 2 时，点 3 的报价被改成了 5，我们又把 (5, 3) 扔进了优先队列！

此时，优先队列里同时存在着两个针对 3 号点的记录。然而，C++ 标准库的 priority_queue 是不支持随机删除内部元素的，难道要把那个过期的 (6, 3) 揪出来删掉吗？

不需要！我们采用极为优美的懒惰删除（Lazy Deletion）策略：

因为优先队列是小根堆，更优秀的 (5, 3) 一定会先出堆，从而将 3 号点的真正最短路敲定为 5； 等到后来那个破烂报价 (6, 3) 慢悠悠晃到堆顶出堆时，我们只需轻巧地查验一下：

if (du != dis[u]) continue; // 发现当前出堆的报价比最优报价还要劣，说明是过期幽灵，直接扔掉！

一行代码，彻底解决重复进堆问题，极其干净利落。

五、核心模板一：单源非负权最短路（Dijkstra 满分标程）

1. 输入输出协议与数据范围

• 输入格式：第一行输入三个整数 $n, m, s$，分别表示节点数、有向边数以及源点编号。接下来 $m$ 行，每行输入三个整数 $u, v, w$，表示一条从 $u$ 到 $v$ 权值为 $w$ 的有向边（保证 $w \ge 0$）。
• 输出格式：输出一行 $n$ 个整数，分别表示源点 $s$ 到各节点 $1 \sim n$ 的最短距离。若某个节点不可达，输出 -1。两数之间用空格隔开。
• 数据范围：$1 \le n, m \le 2 \times 10^5$，$0 \le w \le 10^9$。累计路径长度必须使用 long long 存储。
• 复杂度：时间复杂度 $O((n + m) \log n)$，空间复杂度 $O(n + m)$。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=200005;
const int INF=(1LL<<62);

struct Edge{
	int v,w;
};

vector<Edge> g[N];
int dis[N];
int n,m,s;

void dijkstra(int s){
	for(int i=1;i<=n;i++) dis[i]=INF;
	priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> q;
	
	dis[s]=0;
	q.push({0,s});
	
	while(!q.empty()){
		int du=q.top().first;
		int u=q.top().second;
		q.pop();
		
		// 懒惰删除：若出堆报价不是最新最佳值，直接忽略
		if(du!=dis[u]) continue;
		
		for(int i=0;i<g[u].size();i++){
			int v=g[u][i].v;
			int w=g[u][i].w;
			if(du+w<dis[v]){
				dis[v]=du+w;
				q.push({dis[v],v});
			}
		}
	}
}

void solve(){
	cin>>n>>m>>s;
	for(int i=1;i<=m;i++){
		int u,v,w;
		cin>>u>>v>>w;
		g[u].push_back({v,w});
	}
	
	dijkstra(s);
	
	for(int i=1;i<=n;i++){
		cout<<(dis[i]==INF?-1:dis[i])<<(i==n?'\n':' ');
	}
}

signed main(){
	ios::sync_with_stdio(0),cin.tie(0);
	solve();
	return 0;
}

六、负权边的幽灵：Bellman-Ford 与负环检测

1. 负权边直接打碎了 Dijkstra 的贪心基石

看一个最纯粹的反例： 节点 1 到 2 权值 2，节点 1 到 3 权值 5，节点 3 到 2 权值 -10。

• Dijkstra 从 1 出发，看到当前最小的未确定点是 2（距离 2），会直接宣布：“到 2 的最短距离就是 2！”
• 但实际上，只要绕到 3 再走向 2，总花费是 $5 + (-10) = -5$，比 2 便宜得多！

整张图连环都没有，仅仅因为一条负权边的出现，Dijkstra 赖以生存的贪心假设就荡然无存。

2. 负权边 $\neq$ 负环

• 负权边：单纯的一条倒贴钱的边。只要没有负权环，最短路仍然是完全有解且客观存在的（例如上面到 2 的最短距离就是 -5）。
• 负环（负权回路）：一个环上的所有边权相加之和为负数！ 如果有一条路径经过了这个负环，你就可以在这个环里无限“刷圈”。每多绕一圈，总花费就减少一部分。花费可以奔向 $-\infty$，最短路彻底失去有限下界！

3. Bellman-Ford 的物理本质：一条简单最短路至多包含 $n-1$ 条边

Bellman-Ford 不搞任何贪心，它极其质朴地执行轮次扫描： 每一轮，把图上所有的边无差别地拿出来松弛一遍。

数学铁律（抽屉原理）： 在一张没有负环的图中，任意两点间的最短路必然是一条简单路径（不包含重复节点）。$n$ 个点的简单路径，最多只能包含 $n-1$ 条边。

• 第 1 轮扫描，至少能保证包含 1 条边的最短路径全部收敛；
• 第 2 轮扫描，至少能保证包含 2 条边的最短路径全部收敛；
• ……
• 扫满 $n-1$ 轮后，全图所有的最短路必然已经完全确定！

如果我们在第 $n$ 轮扫描时，发现竟然还有边能够被成功松弛？ 这就说明这条路径上包含了至少 $n$ 条边（即 $n+1$ 个点）。根据抽屉原理，路径上必然出现了重复节点——全图必定存在从源点可达的负权环！

4. 核心实现片段：单源负环检测

struct BFEdge { int u, v; int w; };

// 返回 true 表示无负环且已收敛，返回 false 表示检测到源点可达的负环
bool bellman(int n, int s, const vector<BFEdge>& edges, vector<int>& dis) {
	dis.assign(n + 1, INF);
	dis[s] = 0;
	
	for (int round = 1; round <= n; round++) {
		bool changed = false;
		for (int i = 0; i < edges.size(); i++) {
			int u = edges[i].u, v = edges[i].v, w = edges[i].w;
			if (dis[u] != INF && dis[u] + w < dis[v]) {
				dis[v] = dis[u] + w;
				changed = true;
			}
		}
		// 若某一轮没有任何一条边被松弛，说明全图提前收敛，直接大功告成
		if (!changed) return true;
		// 到了第 n 轮依然能松弛，铁证如山：存在可达负环！
		if (round == n) return false;
	}
	return true;
}

💡 全图负环侦测技巧：上面的函数检测的是“从特定源点 $s$ 出发能否走到负环”。如果要检测整张图任意角落是否存在负环，只需设立一个虚拟的超级源点 0，向 $1 \sim n$ 的每一个节点都连一条权值为 0 的单向边，然后以 0 为源点跑判定。此时总节点数变为 $n+1$，传入函数的节点总数参数也需相应改为 $n+1$。

七、全源最短路的动态规划：Floyd-Warshall

如果题目不满足于“从某一个源点出发”，而是需要我们回答任意两点 $(i, j)$ 之间的最短路呢？

点数极小（$n \le 400$）时，Floyd-Warshall 是代码最简短、杀伤力最广的终极武器。

1. 状态定义与“阶段”的哲学

很多人把 Floyd 看作三重暴力的嵌套，这是极大的误解。Floyd 的底层是极其典雅的动态规划。

我们定义灵魂状态 $d[k][i][j]$： 只允许借助编号在 $1 \sim k$ 范围内的节点作为“中转跳板”时，从节点 $i$ 走到节点 $j$ 的最短距离。

当我们要考虑把新节点 $k$ 加入中转跳板集合时，面对路线 $i \to j$，我们只有两种选择：

1. 完全不借道 $k$：那么距离依旧维持上一阶段的成果，即 $d[k-1][i][j]$；
2. 借道 $k$ 实施中转：路径被折叠成两半——先从 $i$ 走到 $k$，再从 $k$ 走到 $j$！总花费为 $d[k-1][i][k] + d[k-1][k][j]$。

两者取较小值，在滚动数组降维后，得到了大家耳熟能详的极简转移方程：

2. 考场最高频死穴：为什么循环中 $k$ 必须在最外层？

绝大多数考场写挂 Floyd 的同学，都把循环写成了 for i, for j, for k。

必须反复强调：$k$ 代表的是动态规划的“阶段”，必须作为最外层循环！ 只有当“只允许使用 $1 \sim k-1$ 中转的所有点对最短路”全部算得清清楚楚之后，你才有资格引入第 $k$ 个点作为新的垫脚石。

直观反例：考虑一条单向链 $1 \to 4 \to 3 \to 2$，每条边权均为 1。 如果你把 $k$ 放在最内层，当最外层遍历到 $(i=1, j=2)$ 时，$k$ 会尝试 1, 2, 3, 4 作为中转点。然而在此时，因为 $1 \to 3$ 的实际距离根本还没有被计算出来，$1 \to 2$ 借道 3 的松弛尝试就会当场落空！后续再也没有机会回过头来拯救它，整张表彻底坍塌。

八、核心模板二：多次点对询问与负环拦截（Floyd 满分标程）

1. 输入输出协议与数据范围

• 输入格式：第一行输入三个整数 $n, m, q$，分别表示节点数、有向边数和询问次数。接下来的 $m$ 行，每行输入三个整数 $u, v, w$，表示一条从 $u$ 到 $v$ 权值为 $w$ 的有向边。随后 $q$ 行，每行两个整数 $u, v$，表示一次询问。
• 输出格式：若图中存在负环，直接输出一行 NEGATIVE CYCLE 并终止程序；若无负环，针对每个询问输出其最短路径长度，若不可达则输出 INF。
• 数据范围：$1 \le n \le 400$，$1 \le m \le 10^5$，$1 \le q \le 10^5$，边权绝对值 $|w| \le 10^9$。
• 复杂度：时间复杂度 $O(n^3 + q)$，空间复杂度 $O(n^2)$。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=405;
const int INF=(1LL<<62);

int d[N][N];
int n,m,q;

void solve(){
	cin>>n>>m>>q;
	
	// 1. 初始化邻接矩阵
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			if(i==j) d[i][j]=0;
			else d[i][j]=INF;
		}
	}
	
	for(int i=1;i<=m;i++){
		int u,v,w;
		cin>>u>>v>>w;
		d[u][v]=min(d[u][v],w); // 重边必须取最小值
	}
	
	// 2. Floyd 核心转移：阶段 k 必须在最外层！
	for(int k=1;k<=n;k++){
		// 负环拦截：自环出现负数，说明存在从 k 出发绕一圈再回到 k 的负权回路
		if(d[k][k]<0){
			cout<<"NEGATIVE CYCLE\n";
			return;
		}
		for(int i=1;i<=n;i++){
			if(d[i][k]==INF) continue; // 无法到达中转点，跳过
			for(int j=1;j<=n;j++){
				if(d[k][j]==INF) continue; // 中转点无法到达目标，跳过
				d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
			}
		}
	}
	
	// 3. 响应多次点对询问
	while(q--){
		int u,v;
		cin>>u>>v;
		if(d[u][v]==INF) cout<<"INF\n";
		else cout<<d[u][v]<<'\n';
	}
}

signed main(){
	ios::sync_with_stdio(0),cin.tie(0);
	solve();
	return 0;
}

九、降维建图巧思：反图与超级源点

在真实赛场上，单纯考抄写模板的题目凤毛麟角。真正的高手，往往通过巧妙改建图纸，用基础算法优雅通关。

1. 建立反图：多对一最短路的瞬间降维

• 痛点：全图有 $n$ 个点，现在要问：所有点跑到同一个终点 $T$ 的最短路。
• 暴力做法：以每个点为源点跑 $n$ 次 Dijkstra，复杂度直接乘上 $n$，当场 TLE。
• 高维打法：我们把所有的有向边全部倒转——原图中的 $u \to v$（权值 $w$），在反图中变成 $v \to u$（权值 $w$）。 原图中从各个点汇聚到 $T$ 的路线，在反图中正好对应从 $T$ 出发辐射到各个点的路线！ 我们只需要在反图上以 $T$ 为源点跑单次 Dijkstra，就能在 $O((n+m)\log n)$ 的时间内一口气拿到所有点到 $T$ 的距离。

2. 超级源点：把多起点起跑线强行拉平

• 痛点：图中有若干个候选起点 $S_1, S_2, \dots, S_k$，你可以从其中任意一个出发，求到达终点的最小代价。
• 高维打法：建立一个虚拟节点 0（超级源点）。从 0 号点向每一个 $S_i$ 连一条权值为 0 的有向边。 从 0 号点跑一次单源最短路，就完全等价于所有起点在同一瞬间并排起跑，哪个起点最近，哪个起点就会先破局而出！

3. 点权转化为边权

如果收费标准不是立在“道路”上，而是立在“城市”里（进入城市 $v$ 需缴纳过路费 $cost[v]$），怎么办？ 把账目算清：将所有指向节点 $v$ 的入边的权值，全部增加 $cost[v]$。只要入城就必须买单，建图完成后，节点重新变为空白中转点，直接套用标准最短路算法。

十、终极思维跃迁：分层图与状态空间建图

这是整篇讲义最具实战含金量的升维杀招。

1. 什么是状态？为什么节点编号骗了你？

初学者常常把图论中的“点”，机械地对应为物理世界的一个坐标（比如“2号城市”）。

但在图论的深层世界中，图的本质是状态机！一个“点”代表的，是你在做出决策时所处的所有现实约束的集合。

2. 经典痛点：免费走 $k$ 条边

假设有一道经典题目：从起点走到终点，途中你拥有特权，最多可以免费通过 $k$ 条边。求最小花费。

如果你依然用一维数组 dis[u] 来记录“到达城市 $u$ 的最小花费”，你会立刻遭遇逻辑灭顶之灾：

看一个刺眼的极简反例： 一条有向链：$1 \to 2$（权 1）、$2 \to 3$（权 100），你手握 1 次 免费特权。

当我们走到 2 号点时，其实存在着两种完全不同的人生状态：

• 状态 A：花费了 1 元，但把宝贵的免费特权捏在手里（未消耗）；
• 状态 B：花费了 0 元（在 $1 \to 2$ 上直接挥霍了免费机会），但特权彻底耗尽。

如果你的代码只认一维距离，它会看到状态 B 花费为 0，比状态 A 的 1 更便宜，从而自作聪明地把状态 A 判定为“劣解”直接抹杀掉！ 接下来面对 $2 \to 3$（权 100）这条长边，因为特权早已用尽，你只能硬着头皮付 100 元，总花费变成了 $0 + 100 = 100$ 元！

但真正的最优决策是：宁可一开始花 1 元（保留状态 A），把免费机会留给昂贵的 $2 \to 3$，最终总花费仅为 $1 + 0 = 1$ 元！

3. 分层图建模：在平行空间中跃迁

为了不让关键状态被错误淘汰，我们必须把“维度”升上去： 定义灵魂数组 dis[u][c]：到达节点 $u$，且已经使用了 $c$ 次免费特权时的最少花费。

原图中的每一条边 $u \to v$（权值 $w$），在状态空间中分裂为两种完全不同的合法操作：

1. 老老实实买单（在同一层平行世界穿行）： 不消耗免费次数，从 $(u, c)$ 转移到 $(v, c)$，边权为 $w$；
2. 动用特权免单（向上一层平行世界跃迁）： 若当前已用次数 $c < k$，则可以消耗一次机会，从 $(u, c)$ 飞跃到 $(v, c+1)$，边权直接降为 0！

4. 核心实现片段：分层图 Dijkstra

long long layered(int n, int k, int s, int t, const vector<vector<Edge>>& g) {
    vector<vector<long long>> dis(n + 1, vector<long long>(k + 1, INF));
    using State = tuple<long long, int, int>;
    priority_queue<State, vector<State>, greater<State>> q;
    
    dis[s][0] = 0;
    q.push(make_tuple(0, s, 0));
    
    while (!q.empty()) {
        State cur = q.top(); q.pop();
        long long du = get<0>(cur);
        int u = get<1>(cur), c = get<2>(cur);
        
        // 懒惰删除
        if (du != dis[u][c]) continue;
        
        for (auto e : g[u]) {
            // 选择 1：正常花钱走，层数不变
            if (du + e.w < dis[e.v][c]) {
                dis[e.v][c] = du + e.w;
                q.push(make_tuple(dis[e.v][c], e.v, c));
            }
            // 选择 2：使用特权免单，层数 c + 1（要求 c < k）
            if (c < k && du < dis[e.v][c + 1]) {
                dis[e.v][c + 1] = du;
                q.push(make_tuple(du, e.v, c + 1));
            }
        }
    }
    
    // 关键细节：题目要求“最多免费 k 次”，不代表必须强迫用满 k 次！
    // 答案应为到达终点所有层数的最小值
    return *min_element(dis[t].begin(), dis[t].end());
}

💡 空间与时间估算： 分层图将节点规模扩大到了 $n \times (k+1)$，边数同样成倍放大。时间复杂度为 $O((n+m)k \log(nk))$。写分层图之前，务必心算一下内存上限，杜绝盲目开层导致 MLE。

十一、最短路方案恢复：不要只拿报销结果，要保留行程单

场景：题目不仅问你从起点到终点最少花多少钱，还要求你输出具体走了哪些城市。

我们在执行松弛操作时，一直在关注“能不能变便宜”。其实，每一次成功把 dis[v] 刷新变小，就意味着我们找到了一段更优的“前驱关系”——是因为谁，我才变得这么便宜？

1. 记录前驱的物理意义

增加一个灵魂数组 pre[N]。 在松弛成功的那个瞬间：

if (dis[u] + w < dis[v]) {
    dis[v] = dis[u] + w;
    pre[v] = u;  // 记录：是 u 把我拉过来的！
}

这就像财务报销：只要我换了更便宜的路线，我就把上一站的城市写进 pre 里。等到整个算法结束，pre[T] 存的就是终点 $T$ 的上一站，pre[pre[T]] 就是上上站……一路倒推，必定能顺藤摸瓜回到起点 $S$！

2. 核心代码片段：顺藤摸瓜与翻转

因为我们是从终点往前找，找出来的路径是反的，需要借助 vector 翻转一下。注意，寻路前务必先确认终点是否真的可达！

vector<int> path;
if (dis[T] == INF) {
    cout << "No path\n";
    return;
}

int curr = T;
// 假设起点的前驱 pre[S] 初始为 0
while (curr != 0) {
    path.push_back(curr);
    curr = pre[curr];
}
// 翻转得到 S -> ... -> T
reverse(path.begin(), path.end()); 

for (int i = 0; i < path.size(); i++) {
    cout << path[i] << (i == path.size() - 1 ? "" : " ");
}
cout << '\n';

十二、最短路计数：加法原理与零权陷阱

场景：求起点到终点的最短路径共有多少条（往往要求对大质数取模）。

1. 状态转移与覆盖

增加一个数组 cnt[N]，表示“从起点到节点 $v$ 的最短路条数”。起点初始化 cnt[S] = 1。

在松弛时，有两种情况会触发计数变化：

1. 发现了更短的路 (dis[u] + w < dis[v])：旧路线全部作废！条数直接继承更优者的条数。 cnt[v] = cnt[u];
2. 发现了长度一模一样的平替路线 (dis[u] + w == dis[v])：说明找到了新的等价方案，条数累加。 cnt[v] = (cnt[v] + cnt[u]) % MOD;

2. 致命陷阱：为什么零权边会把计数砸烂？

上面的逻辑在严格正权图中用 Dijkstra 跑是完全正确的。但在存在 0 权边 的图中，这套边走边加的简单逻辑就会严重翻车。

常见的 Dijkstra 写法只有在距离严格变短时才会将点重新推入优先队列。面对 0 权边带来的“等长平替路径”，它可能因为出队顺序的问题，直接漏掉等长路径的贡献传递。更极端的是，如果图中存在 0 权环，那在这个环里绕多少圈距离都不会增加，最短路的条数实际上可能是无穷大！

💡 教练提醒： 在有 0 权边的图中做最短路计数，标准打法是：先用 Dijkstra 求出全图的最短路距离，然后把所有满足 dis[u] + w == dis[v] 的边单独抽出来建一张新图。只要原图没有 0 权环，这张新图必定是一个有向无环图（DAG），最后在这个 DAG 上跑拓扑排序和 DP 计数即可。

十三、差分约束系统入门（选学）

先修要求：熟练掌握 Bellman-Ford，理解负权环的物理意义。

场景：给你一堆形如 $x_A - x_B \le 5$ 的不等式，让你求一组满足所有未知数条件的解。

这不是代数课吗，关图论什么事？ 仔细看看松弛的终极条件：当最短路算法收敛结束时，图上任何一条从 $u$ 到 $v$ 权值为 $w$ 的边，都必须满足：

把它移个项：

震撼的映射：这不就是题面里的不等式 $x_v - x_u \le w$ 吗！代数世界里的不等式，完美对应了图论世界里的一条有向边。

1. 建边方向：认准“被约束者”

对于不等式 $x_v - x_u \le w$，化为 $x_v \le x_u + w$。 它的物理意义是：$x_v$ 的上限被 $x_u$ 卡住了。 在图论里，就是从 $u$ 向 $v$ 连一条权值为 $w$ 的有向边。

• 如果题目给的是 $x_A - x_B \ge 3$ 怎么办？ 两边同乘 $-1$ 变号：$x_B - x_A \le -3$，然后从 $A$ 向 $B$ 连一条权值为 $-3$ 的边。
• 如果给的是 $x_A = x_B$？ 拆成 $x_A - x_B \le 0$ 和 $x_B - x_A \le 0$，互相连权值为 0 的双向边。

2. 无解的物理意义：逻辑自相矛盾与负环

建好图后，我们建立一个超级源点跑一次含有负权边的最短路算法（通常用 Bellman-Ford）。

• 如果跑出了负环：说明存在逻辑死结。 比如 $A \to B$ (权 -2)，$B \to A$ (权 -1)。也就是 $x_B \le x_A - 2$ 且 $x_A \le x_B - 1$。 代入一下就是 $x_A \le x_A - 3$，绝对矛盾！所以只要图中有负环，差分约束系统必然无解。
• 如果没有负环：最后跑出来的 dis 数组，就是原不等式组的一组合法解！

3. 核心模板三：差分约束验证程序（基于 Bellman-Ford）

输入输出协议与数据范围

• 输入格式：第一行 $n, m$，表示未知数个数和不等式个数。接下来 $m$ 行每行输入 $u, v, w$，表示一条约束 $x_v - x_u \le w$。
• 输出格式：若无解输出 NO；若有解则输出 $n$ 个整数代表 $x_1 \sim x_n$ 的一组合法相对解。
• 数据范围：$1 \le n \le 5000$，$1 \le m \le 10000$，$-10^4 \le w \le 10^4$。

#include<bits/stdc++.h>
#define int long long
using namespace std;

const int N = 5005;
const int INF = (1LL << 60);

struct Edge {
    int u, v, w;
};

vector<Edge> edges;
int dis[N];
int n, m;

// 返回 true 表示有解，false 表示无解（存在逻辑矛盾造成的负环）
bool bellman_ford(int s) {
    // 初始将所有未知数设为极大值
    for(int i = 0; i <= n; i++) dis[i] = INF;
    dis[s] = 0;
    
    // 加入超级源点后，全图共 n+1 个点。
    // 根据抽屉原理，无负环图的最长简单路径最多包含 n 条边。
    // 因此我们需要扫描 n+1 轮：前 n 轮用于收敛最短路，第 n+1 轮专门用来抓负环。
    for(int round = 1; round <= n + 1; round++) {
        bool changed = false;
        for(int i = 0; i < edges.size(); i++) {
            int u = edges[i].u;
            int v = edges[i].v;
            int w = edges[i].w;
            if(dis[u] != INF && dis[u] + w < dis[v]) {
                dis[v] = dis[u] + w;
                changed = true;
            }
        }
        // 如果某一轮没有任何边被松弛，说明已经提前收敛，必然有解
        if(!changed) return true; 
        
        // 如果到了第 n+1 轮依然有边在松弛，铁证如山：必然存在负权回路
        if(round == n + 1) return false; 
    }
    return true;
}

void solve() {
    cin >> n >> m;
    for(int i = 1; i <= m; i++) {
        int u, v, w;
        // 读入 u v w，代表 x_v - x_u <= w
        cin >> u >> v >> w; 
        edges.push_back({u, v, w});
    }
    
    // 建立超级源点 0，强行将 0 连接到 1~n 所有节点，权值为 0
    // 相当于增加约束 x_i - x_0 <= 0，即限制 x_i <= 0，同时确保所有点在图上连通
    for(int i = 1; i <= n; i++) {
        edges.push_back({0, i, 0});
    }
    
    if(!bellman_ford(0)) {
        cout << "NO\n";
    } else {
        // 输出这组合法的相对解
        for(int i = 1; i <= n; i++) {
            cout << dis[i] << (i == n ? "" : " ");
        }
        cout << '\n';
    }
}

signed main() {
    ios::sync_with_stdio(0), cin.tie(0);
    solve();
    return 0;
}
/*
自拟样例：
输入：
3 3
1 2 5
2 3 -2
1 3 4
输出：
0 0 -2

解释：
对应的约束为：
x_2 - x_1 <= 5
x_3 - x_2 <= -2
x_3 - x_1 <= 4
输出的解 (x_1=0, x_2=0, x_3=-2) 完美满足所有不等式。
*/

十四、渐进式实战练习题单

1. 第一阶段：模板肌肉记忆与基本功

1. 洛谷 P4779 【模板】单源最短路径（标准版）
   • 训练指引：反复默写堆优化 Dijkstra，做到对 if (du != dis[u]) continue; 形成生理本能反应。
2. 洛谷 B3647 【模板】Floyd
   • 训练指引：闭眼默写 Floyd，死死焊牢最外层的中转点 $k$ 循环。原题是无向连通正权图，允许重边，读边时两个方向都要取 min：d[u][v]=min(d[u][v],w);、d[v][u]=min(d[v][u],w);。本讲第八节完整程序采用有向图的自拟协议，读入、询问和输出都要按原题适配，不能整份照抄提交。

2. 第二阶段：建图巧思与思维跃迁

3. 洛谷 P1629 邮递员送信
   • 训练指引：从邮局去所有村庄，再从所有村庄返回邮局。去程跑正图，回程跑反图，感受反向建图带来的极致性能提升。
4. 洛谷 P3385 【模板】负环
   • 训练指引：本题只问从 1 号点能到达的负环，从 1 出发检测即可，别加超级源点把不连通的负环也算进去。建图时注意：非负边双向连，负边只按输入方向连。

3. 第三阶段：分层图与状态空间实战

5. 洛谷 P4568 [JLOI2011] 飞行路线
   • 训练指引：最多免费搭乘 $k$ 次航线的绝对经典。深刻理解“多维状态坐标”以及终点取 *min_element 的物理本质。