SPFA + 链式前向星

只有20分qaq

#include <iostream>
#include <queue>
using namespace std;

#define INF 2147483647

struct Edge
{
	int to, w, next;
};
Edge ed[500010];

int head[500010];
int cnt, n, m, s;

void addEdge(int u, int v, int w)
{
	ed[++cnt].next = head[u];
	ed[cnt].to = v;
	ed[cnt].w = w;
	head[u] = cnt;
}

queue<int> q;

int dis[500010];
bool vis[500010];

void SPFA()
{
	for (int i = 1; i <= n; i++)
	{
		dis[i] = INF;
		vis[i] = 0;
	}
	dis[s] = 0;
	vis[s] = 1;
	int tmp = s;
	q.push(s);
	while (!q.empty())
	{
		tmp = q.front();
		q.pop();
		vis[s] = 0;
		for (int i = head[tmp]; i != 0;i=ed[i].next)
		{
			int v = ed[i].to;
			if (ed[i].w+dis[tmp]<dis[v])
			{
				dis[v] = ed[i].w + dis[tmp];
				if (vis[v]==0)
				{
					q.push(v);
					vis[v] = 1;
				}
			}
		}
	}
}

int main()
{
	ios::sync_with_stdio(NULL);
	cin >> n >> m >> s;
	for (int i = 1; i <= m; i++)
	{
		int u, v, w;
		cin >> u >> v >> w;
		addEdge(u, v, w);
	}
	SPFA();
	for (int i = 1; i <= n; i++)
	{
		cout << dis[i] << ' ';
	}
}