P3371 【模板】单源最短路径（弱化版）(C++_SPFA算法_链式向前星)

题目背景

本题测试数据为随机数据，在考试中可能会出现构造数据让SPFA不通过，如有需要请移步 P4779。

题目描述

如题，给出一个有向图，请输出从某一点出发到所有点的最短路径长度。

输入格式

第一行包含三个整数 n,m,s，分别表示点的个数、有向边的个数、出发点的编号。

接下来 m 行每行包含三个整数 u,v,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入队，当队列非空时：

    队首元素（a）出队，对以a为起始点的所有边的终点依次进行松弛操作（此处有b,c,d三个点），此时路径表格状态为：

在松弛时三个点的最短路径估值变小了，而这些点队列中都没有出现，这些点需要入队，此时，队列中新入队了三个结点b,c,d

队首元素b点出队，对以b为起始点的所有边的终点依次进行松弛操作（此处只有e点），此时路径表格状态为：

在最短路径表中，e的最短路径估值也变小了，e在队列中不存在，因此e也要入队，此时队列中的元素为c，d，e

队首元素c点出队，对以c为起始点的所有边的终点依次进行松弛操作（此处有e,f两个点），此时路径表格状态为：

在最短路径表中，e，f的最短路径估值变小了，e在队列中存在，f不存在。因此e不用入队了，f要入队，此时队列中的元素为d，e，f

队首元素d点出队，对以d为起始点的所有边的终点依次进行松弛操作（此处只有g这个点），此时路径表格状态为：

队首元素e点出队，对以d为起始点的所有边的终点依次进行松弛操作，在最短路径表中，g的最短路径估值没有变小（松弛不成功），没有新结点入队，队列中元素为f，g

队首元素f点出队，对以f为起始点的所有边的终点依次进行松弛操作（此处有d，e，g三个点），此时路径表格状态为：

在最短路径表中，e，g的最短路径估值又变小，队列中无e点，e入队，队列中存在g这个点，g不用入队，此时队列中元素为g，e

队首元素g点出队，对以g为起始点的所有边的终点依次进行松弛操作（此处只有b点），此时路径表格状态为：

在最短路径表中，b的最短路径估值又变小，队列中无b点，b入队，此时队列中元素为e，b队首元素e点出队，对以e为起始点的所有边的终点依次进行松弛操作（此处只有g这个点），此时路径表格状态为：

在最短路径表中，g的最短路径估值没变化（松弛不成功），此时队列中元素为b

队首元素b点出队，对以b为起始点的所有边的终点依次进行松弛操作（此处只有e这个点），此时路径表格状态为：

在最短路径表中，e的最短路径估值没变化（松弛不成功），此时队列为空了

最终a到g的最短路径为１４

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再来！