wa 50pts

评测记录

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
const int N = 1e5 + 10, M = 5e5 + 10;
int n, st, ed, dis[N];
int wt[M], hd[M], nxt[M], edg[M], idx;
bool vis[N];
void spfa()
{
	memset(dis, 0x3f, sizeof dis);
	dis[st] = 0;
	queue <int> q;
	q.push(st);
	vis[st] = true;
	while (!q.empty())
	{
		int t = q.front();
		q.pop();
		vis[t] = false;
		for (int i = hd[t]; i != -1; i = nxt[i])
			if (dis[t] + wt[i] < dis[edg[i]])
			{
				dis[edg[i]] = dis[t] + wt[i];
				if (!vis[i])
				{
					q.push(edg[i]);
					vis[edg[i]] = true;
				}
			}
	}
}
void add(int a, int b, int c)
{
	wt[++idx] = c;
	edg[idx] = b;
	nxt[idx] = hd[a];
	hd[a] = idx;
}
int main()
{
	memset(nxt, -1, sizeof nxt);
	int a, b, c, t;
	cin >> n >> t >> st;
	for (int i = 1; i <= t; i++)
	{
		cin >> a >> b >> c;
		add(a, b, c);
	}
	spfa();
	for (int i = 1; i <= n; i++)
		cout << dis[i]<<' ';
	return 0;
}