Acwing851题spfa求最短路如何为？

47.Acwing基础课第851题-简单-spfa求最短路 题目描述 给定一个 n个点 m 条边的有向图，图中可能存在重边和自环， 边权可能为负数。 请你求出 1号点到 n 号点的最短距离，如果无法从 1 号点走到 n 号点，则输出 impossible。 数据保证不存在负权回路。 输入格式 第一行包含整数 n 和 m。 接下来 m 行每行包含三个整数 x,y,z，表示存在一条从点 x 到点 y 的有向边，边长为 z。 输出格式 输出一个整数，表示 1 号点到 n 号点的最短距离。 如果路径不存在，则输出 impossible。 数据范围 1≤n,m≤105 图中涉及边长绝对值均不超过 10000。 输入样例： 3 3 1 2 5 2 3 -3 1 3 4 输出样例： 2 代码： #include <cstring> #include <iostream> #include <algorithm> #include <queue> using namespace std; const int N = 100010, INF = 0x3f3f3f3f; int n, m; int h[N], w[N], e[N], ne[N], idx; int dist[N]; bool st[N]; void add(int a, int b, int c) { e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ; } int spfa() { memset(dist, 0x3f, sizeof dist); dist[1] = 0; queue<int> q; q.push(1); st[1] = true; while (q.size()) { int t = q.front(); q.pop(); st[t] = false; for (int i = h[t]; i != -1; i = ne[i]) { int j = e[i]; if (dist[j] > dist[t] + w[i]) { dist[j] = dist[t] + w[i]; if (!st[j]) { q.push(j); st[j] = true; } } } } return dist[n]; } int main() { scanf("%d%d", &n, &m); memset(h, -1, sizeof h); while (m -- ) { int a, b, c; scanf("%d%d%d", &a, &b, &c); add(a, b, c); } int t = spfa(); if (t > INF/2) puts("impossible"); else printf("%d\n", t); return 0; } 一、 代码结构与数据结构分析 1. 头文件与全局变量 #include <cstring> // 用于 memset #include <iostream> #include <algorithm> #include <queue> // SPFA 需要用到队列 using namespace std; const int N = 100010; // 最大点数，通常根据题目范围设定 int n, m; // n: 点数，m: 边数 // 邻接表四件套 int h[N], w[N], e[N], ne[N], idx; int dist[N]; // dist[i] 存储从起点 1 到 i 的最短距离 bool st[N]; // state数组，st[i] = true 表示节点 i 当前在队列中 核心数据结构解释（邻接表）： 这是一种用数组模拟链表的存图方式，适合存储稀疏图（点多边少）。 h[N] (Head)：头结点数组。h[a] 存储的是从节点 a 出发的第一条边在数组中的索引。 e[N] (Edge/End)：终点数组。e[i] 表示索引为 i 的这条边指向哪个节点。 w[N] (Weight)：权值数组。w[i] 表示索引为 i 的这条边的长度 / 花费。 ne[N] (Next)：下一条边数组。ne[i] 表示与索引为 i 的边同起点的下一条边的索引。 idx：当前边的计数器。每加一条边，idx++。 2. 邻接表加边函数 add void add(int a, int b, int c) { e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ; } 这是经典的 “头插法”。我们要添加一条从 a 指向 b，权值为 c 的边： e[idx] = b：记录这条边的终点是 b。 w[idx] = c：记录这条边的权重是 c。 ne[idx] = h[a]：让这条边的 “下一条边” 指向 a 当前的第一条边（插队）。 h[a] = idx++：让 a 的头指针指向这条新边，然后索引 idx 自增。 图解记忆：就像往链表头部插入新节点。 二、 SPFA 核心算法逻辑详解 int spfa() { // 1. 初始化距离数组 memset(dist, 0x3f, sizeof dist); dist[1] = 0; // 2. 初始化队列 queue<int> q; q.push(1); st[1] = true; // 3. 核心循环 while (q.size()) { int t = q.front(); // 取出队头 q.pop(); st[t] = false; // 标记：t 已不在队列中 // 4. 遍历 t 的所有出边（松弛操作） for (int i = h[t]; i != -1; i = ne[i]) { int j = e[i]; // j 是这条边的终点 if (dist[j] > dist[t] + w[i]) { dist[j] = dist[t] + w[i]; // 更新最短路 if (!st[j]) // 如果 j 不在队列中 { q.push(j); // 入队 st[j] = true; // 标记入队 } } } } return dist[n]; } 1.逐段拆解： 初始化 (memset)： memset(dist, 0x3f, sizeof dist);：将所有距离初始化为一个很大的值（0x3f3f3f3f，约为 109）。 为什么用 0x3f？ 一是因为它足够大，超过题目中通常的边权上限；二是因为 0x3f3f3f3f + 0x3f3f3f3f 不会超出 int 的范围（不会溢出），方便后续比较。 dist[1] = 0：默认起点是节点 1，到自己的距离为 0。 队列与标记： 把起点 1 推入队列。 st[1] = true：st 数组的作用是防止同一个节点在队列里重复出现。如果节点 j 已经在队列里等着被处理了，我们只需要更新它的 dist 值即可，不需要再把它塞进去一次。 核心循环 (while)： 只要队列不空，就说明还有节点可能更新其他节点的最短路。 取出队头 t，弹出队列，并把 st[t] 设为 false（现在它出来了，以后还能再进去）。 松弛操作 (Relaxation)： 遍历 t 的所有邻居 j。 逻辑：如果 起点 -> t -> j 的距离比之前记录的 起点 -> j 更短，那就更新。 更新后：既然 j 的最短路变短了，那么通过 j 去更新 j 的邻居就有可能变得更优。所以如果 j 不在队列里，就把它塞进去。 2.基于 SPFA 算法的图迭代更新全流程详解 （1）前置准备：图的边信息与代码初始化 ①图的有向边梳理 该图共 5 个节点（n=5）、7 条有向边，边信息如下： 起点 a 终点 b 权值 c 1 2 3 1 3 2 2 4 1 4 1 4 4 3 6 4 5 4 5 3 4 索引 idx 0 1 2 3 4 5 6 e[idx] (终点) 2 3 4 1 3 5 3 w[idx] (权值) 3 2 1 4 6 4 4 ne[idx] (下一条边) -1 0 -1 -1 3 4 -1 头指针数组 h[1] h[2] h[3] h[4] h[5] 值 1 2 -1 5 6 ②代码核心规则回顾 邻接表用头插法存边，遍历节点出边的顺序是add添加的逆序（不影响最终最短路结果，仅中间遍历顺序不同） dist[i]：起点 1 到节点 i 的最短距离，初始为0x3f3f3f3f（无穷大），起点dist[1]=0 st[i]：标记节点 i 是否在队列中，避免重复入队 核心逻辑：取出队头节点，用该节点的所有出边做松弛操作（更新邻居的最短距离），更新成功且邻居不在队列中则入队 ③初始状态（算法启动前） 节点编号 1 2 3 4 5 dist 数组 0 ∞ ∞ ∞ ∞ st 数组 true false false false false 队列 q：[1]（队头为 1，队尾为 1） 说明：∞ 代表代码中的0x3f3f3f3f，后续统一用∞表示 （2）逐轮迭代更新全流程 第 1 轮循环：处理队头节点 1 1.出队：q.front() = 1，弹出。q 变为空。 2.标记：st[1] = false。 3.遍历边： 边 1->3 (w=2)： 判断：dist[3] (∞) > dist[1] (0) + 2 → 是。 更新：dist[3] = 2。 入队：st[3] 为 false，入队。q = [3]，st[3] = true。 边 1->2 (w=3)： 判断：dist[2] (∞) > dist[1] (0) + 3 → 是。 更新：dist[2] = 3。 入队：st[2] 为 false，入队。q = [3, 2]，st[2] = true。 本轮结束后状态： 节点编号 1 2 3 4 5 dist 数组 0 3 2 ∞ ∞ st 数组 false true true false false 队列 q：[3, 2] 第 2 轮循环：处理队头节点 2 出队：q.front() = 3，弹出。q 变为 [2]。 标记：st[3] = false。 遍历边： 节点 3 没有出边，for 循环不执行。 无更新，无入队。 本轮状态快照： 节点 1 2 3 4 5 dist 0 3 2 ∞ ∞ st false true false false false 队列 q：[ 2 ] 第 3 轮循环：处理节点 2 出队：q.front() = 2，弹出。q 变为空。 标记：st[2] = false。 遍历边： 边 2->4 (w=1)： 判断：dist[4] (∞) > dist[2] (3) + 1 → 是。 更新：dist[4] = 4。 入队：st[4] 为 false，入队。q = [4]，st[4] = true。 本轮状态快照： 节点 1 2 3 4 5 dist 0 3 2 4 ∞ st false false false true false 队列 q：[ 4 ] 第 4 轮循环：处理节点 4 出队：q.front() = 4，弹出。q 变为空。 标记：st[4] = false。 遍历边： 边 4->5 (w=4)： 判断：dist[5] (∞) > dist[4] (4) + 4 → 是。 更新：dist[5] = 8。 入队：st[5] 为 false，入队。q = [5]，st[5] = true。 边 4->3 (w=6)： 判断：dist[3] (2) > dist[4] (4) + 6 → 2 > 10？否。不更新。 边 4->1 (w=4)： 判断：dist[1] (0) > dist[4] (4) + 4 → 0 > 8？否。不更新。 本轮状态快照： 节点 1 2 3 4 5 dist 0 3 2 4 8 st false false false false true 队列 q：[ 5 ] 第 5 轮循环：处理节点 5 出队：q.front() = 5，弹出。q 变为空。 标记：st[5] = false。 遍历边： 边 5->3 (w=4)： 判断：dist[3] (2) > dist[5] (8) + 4 → 2 > 12？否。不更新。 无入队。 本轮状态快照： 节点 1 2 3 4 5 dist 0 3 2 4 8 st false false false false false 队列 q：[ ] (空) 三、 主函数与关键细节 int main() { scanf("%d%d", &n, &m); memset(h, -1, sizeof h); // 邻接表初始化，-1 表示链表结束 while (m -- ) { int a, b, c; scanf("%d%d%d", &a, &b, &c); add(a, b, c); // 注意：这里只加了 a->b，是有向图 } int t = spfa(); if (t == 0x3f3f3f3f) puts("impossible"); // 节点 n 不可达 else printf("%d\n", t); return 0; } 关键细节说明： 邻接表初始化： memset(h, -1, sizeof h); 非常重要。在 spfa 函数的 for 循环中，循环终止条件是 i != -1。我们将所有头指针初始化为 -1，表示初始时没有边。 有向图 vs 无向图： 这段代码默认处理的是 有向图。如果题目是无向图，你需要把边看成双向的，即 add(a, b, c) 之后还要 add(b, a, c)。 关于 0x3f3f3f3f： 注意 memset 是按字节赋值的。int 是 4 个字节，所以填入 0x3f 后，每个 int 就变成了 0x3f3f3f3f。 判断是否可达时，要用 t == 0x3f3f3f3f，不要用 t > 0x3f3f3f3f / 2 这种（虽然那也是一种常见判法），因为这里没有负权环导致的无穷更新。 四、 算法的局限性与改进（进阶） 负权环问题： 这段代码不能检测负权环。如果图中存在一个从起点 1 可以到达的负权环（绕一圈总权值为负），那么最短路可以无限小，程序会陷入死循环（或者超时）。 如何改进？ 增加一个 cnt[N] 数组，记录每个节点的入队次数。如果 cnt[j] >= n，说明经过了至少 n 条边，根据抽屉原理，必然存在环，直接返回存在负环即可。 时间复杂度： 平均情况：O(m)，非常快。 最坏情况：O(nm)（比如被卡成 Bellman-Ford）。在某些卡 SPFA 的题目中（如无负权边的稠密图），请务必使用 堆优化的 Dijkstra。 总结 这是一份非常标准的竞赛级 SPFA 模板。它的核心思想是：只有被更新过距离的节点，才有可能去更新别人的距离，从而用队列避免了 Bellman-Ford 那种盲目遍历所有边的暴力行为。