题目背景

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

题目描述

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

输入格式

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

接下来 mm 行每行包含三个整数 u,v,wu,v,w，表示一条 u \to vu→v 的，长度为 ww 的边。

输出格式

输出一行 nn 个整数，第 ii 个表示 ss 到第 ii 个点的最短路径，若不能到达则输出 2^{31}-1231−1。

#include <stdio.h>
#include <vector>
#include <queue>
using namespace std;

const int MAXV = 10005;
const int INF = 2147483647;

struct Node {
	int v, dis;
	Node(int _v, int _dis) : v(_v), dis(_dis) {}
};

vector<Node> Adj[MAXV];  //邻接表存储图
int d[MAXV];
bool inq[MAXV];

void spfa(int s)
{
	//初始化
	fill(d, d + MAXV, INF);
	fill(inq, inq + MAXV, false);

	//源点入队
	queue<int> Q;
	Q.push(s);
	inq[s] = true;
	d[s] = 0;

	//主体部分
	while (!Q.empty())
	{
		//出队
		int u = Q.front();
		Q.pop();
		inq[u] = false;

		for (int j = 0; j < Adj[u].size(); j++)
		{
			int v = Adj[u][j].v;
			int dis = Adj[u][j].dis;

			if (d[v] > d[u] + dis)
			{
				d[v] = d[u] + dis;
				if (inq[v] == false)
				{
					Q.push(v);
					inq[v] = true;
				}
			}

		}
	}
}

int main(void)
{
	int n, m, s;
	scanf("%d%d%d", &n, &m, &s);

	int u, v, w;
	for (int i = 0; i < m; i++)
	{
		scanf("%d%d%d", &u, &v, &w);
		Adj[u].push_back(Node(v, w));
	}

	spfa(s);

	for (int i = 1; i <= n; i++)
		printf("%d ", d[i]);
}