SPFA 90分, #3 WA,玄关
查看原帖
SPFA 90分, #3 WA,玄关
1047162
蔡涵秋2011楼主2025/1/20 15:04

写了一个 SPFA,写了 23112^{31}-1,但是还是错了。有没有大佬能帮我看下,谢谢。

#include <bits/stdc++.h>
using namespace std;

const int N = 1e4 + 5, M = 5e5 + 5;

struct node
{
	int v, w;
};

bool vis[N];
int n, m, s, dist[N];
vector <node> g[N];

void spfa()
{
	queue <int> q;
	q.push(s);
	memset(dist, 0x7f, sizeof dist);
	vis[s] = true, dist[s] = 0;
	while (!q.empty())
	{
		int now = q.front(); q.pop(); vis[now] = false;
		for (int i = 0; i < g[now].size(); i++)
		{
			int v = g[now][i].v, w = g[now][i].w;
			if (dist[now] != 0x7f && dist[now] + w < dist[v])
			{
				dist[v] = dist[now] + w;
				if (!vis[v])	q.push(v), vis[v] = true;
			}
		}
	}
	for (int i = 1; i <= n; i++)
	{
		if (dist[i] == 0x7f)	cout << "2147483647 ";
		else	cout << dist[i] << " ";
	}
}

int main()
{
	cin >> n >> m >> s;
	for (int i = 1; i <= m; i++)
	{
		int u, v, w;
		cin >> u >> v >> w;
		g[u].push_back({v, w});
	}
	spfa();
	return 0;
}
2025/1/20 15:04
加载中...