P3371 【模板】单源最短路径（弱化版）(C++_SPFA算法_链式向前星)
题目背景
本题测试数据为随机数据，在考试中可能会出现构造数据让SPFA不通过，如有需要请移步 P4779。
题目描述
如题，给出一个有向图，请输出从某一点出发到所有点的最短路径长度。
输入格式
第一行包含三个整数 n,m,s，分别表示点的个数、有向边的个数、出发点的编号。
接下来 m 行每行包含三个整数 u,v,w，表示一条 的，长度为 w 的边。
输出格式
输出一行 n 个整数，第 i 个表示 s 到第 i 个点的最短路径，若不能到达则输出 。
输入输出样例
输入 #1
4 6 1
1 2 2
2 3 2
2 4 1
1 3 5
3 4 3
1 4 4
输出 #1
0 2 4 3
说明/提示
【数据范围】
对于 的数据：，；
对于 的数据：，；
对于 的数据：，；
对于 的数据：，，保证数据随机。
对于真正 的数据，请移步 P4779。请注意，该题与本题数据范围略有不同。
样例说明：
图片1到3和1到4的文字位置调换
思路
模拟过程（摘自SPFA 算法详解(最短路径)有删改）
首先建立起始点a到其余各点的最短路径表格
| a | b | c | d | e | f | g | |
|---|---|---|---|---|---|---|---|
| d[i] | 0 | inf | inf | inf | inf | inf | inf |
首先源点a入队，当队列非空时：
队首元素（a）出队，对以a为起始点的所有边的终点依次进行松弛操作（此处有b,c,d三个点），此时路径表格状态为：
| a | b | c | d | e | f | g | |
|---|---|---|---|---|---|---|---|
| d[i] | 0 | 24 | 8 | 15 | inf | inf | inf |
在松弛时三个点的最短路径估值变小了，而这些点队列中都没有出现，这些点需要入队，此时，队列中新入队了三个结点b,c,d
队首元素b点出队，对以b为起始点的所有边的终点依次进行松弛操作（此处只有e点），此时路径表格状态为：
| a | b | c | d | e | f | g | |
|---|---|---|---|---|---|---|---|
| d[i] | 0 | 24 | 8 | 15 | 30 | inf | inf |
在最短路径表中，e的最短路径估值也变小了，e在队列中不存在，因此e也要入队，此时队列中的元素为c，d，e
队首元素c点出队，对以c为起始点的所有边的终点依次进行松弛操作（此处有e,f两个点），此时路径表格状态为：
| a | b | c | d | e | f | g | |
|---|---|---|---|---|---|---|---|
| d[i] | 0 | 24 | 8 | 15 | 15 | 11 | inf |
在最短路径表中，e，f的最短路径估值变小了，e在队列中存在，f不存在。因此e不用入队了，f要入队，此时队列中的元素为d，e，f
队首元素d点出队，对以d为起始点的所有边的终点依次进行松弛操作（此处只有g这个点），此时路径表格状态为：
| a | b | c | d | e | f | g | |
|---|---|---|---|---|---|---|---|
| d[i] | 0 | 24 | 8 | 15 | 15 | 11 | 19 |
队首元素e点出队，对以d为起始点的所有边的终点依次进行松弛操作，在最短路径表中，g的最短路径估值没有变小（松弛不成功），没有新结点入队，队列中元素为f，g
队首元素f点出队，对以f为起始点的所有边的终点依次进行松弛操作（此处有d，e，g三个点），此时路径表格状态为：
| a | b | c | d | e | f | g | |
|---|---|---|---|---|---|---|---|
| d[i] | 0 | 24 | 8 | 15 | 13 | 11 | 14 |
在最短路径表中，e，g的最短路径估值又变小，队列中无e点，e入队，队列中存在g这个点，g不用入队，此时队列中元素为g，e
队首元素g点出队，对以g为起始点的所有边的终点依次进行松弛操作（此处只有b点），此时路径表格状态为：
| a | b | c | d | e | f | g | |
|---|---|---|---|---|---|---|---|
| d[i] | 0 | 17 | 8 | 15 | 13 | 11 | 14 |
在最短路径表中，b的最短路径估值又变小，队列中无b点，b入队，此时队列中元素为e，b队首元素e点出队，对以e为起始点的所有边的终点依次进行松弛操作（此处只有g这个点），此时路径表格状态为：
| a | b | c | d | e | f | g | |
|---|---|---|---|---|---|---|---|
| d[i] | 0 | 17 | 8 | 15 | 13 | 11 | 14 |
在最短路径表中，g的最短路径估值没变化（松弛不成功），此时队列中元素为b
队首元素b点出队，对以b为起始点的所有边的终点依次进行松弛操作（此处只有e这个点），此时路径表格状态为：
| a | b | c | d | e | f | g | |
|---|---|---|---|---|---|---|---|
| d[i] | 0 | 17 | 8 | 15 | 13 | 11 | 14 |
在最短路径表中，e的最短路径估值没变化（松弛不成功），此时队列为空了
最终a到g的最短路径为１４
| a | b | c | d | e | f | g | |
|---|---|---|---|---|---|---|---|
| d[i] | 0 | 17 | 8 | 15 | 13 | 11 | 14 |
Code
图的存储采用链式向前星，不懂请点击<这里>
（看完模拟过程和链式向前星的你可以自己写出来么，建议先自己上手试试，代码很简单。）
#include<bits/stdc++.h>//SPFA算法
using namespace std;
#define INF (1<<31)-1
class node
{
public:
int to, next, w;
}edge[500010];
int n, m, s, u, v, w, cnt = 0, head[10010], vis[10010];
long long dis[10010];
queue<int> a;
void add(int u, int v, int w)//链式向前星
{
edge[++cnt].w = w;
edge[cnt].to = v;
edge[cnt].next = head[u];
head[u] = cnt;
}
void SPFA()
{
for (int i = 1; i <= n; i++)
dis[i] = INF;
a.push(s);
vis[a.front()] = 1;
dis[s] = 0;//源点到自身的距离为零
while (!a.empty())
{
for (int i = head[a.front()]; i; i = edge[i].next)//对相连的点进行松弛操作
if (dis[edge[i].to] > dis[a.front()] + edge[i].w)//更新距离
{
dis[edge[i].to] = dis[a.front()] + edge[i].w;
if (!vis[edge[i].to])//队列中无此结点
{
a.push(edge[i].to);
vis[edge[i].to] = 1;
}
}
vis[a.front()] = 0;
a.pop();
}
}
int main()
{
cin >> n >> m >> s;
for (int i = 1; i <= m; i++)//存图
{
cin >> u >> v >> w;
add(u, v, w);
}
SPFA();
for (int i = 1; i <= n; i++)
cout << dis[i]<<" ";
return 0;
}
如果你看懂了SPFA，那么最后这张图送给你：
死因：毒瘤数据。
所以在没有负环（某个重复进入队列的节点）的情况下不建议使用SPFA,请放心随机数据的话肯定会有，出题人要是想卡SPFA那就请换Dijkstra再来！