90pts求调
查看原帖
90pts求调
685260
ZettaByte楼主2024/3/3 13:14

太丢人现眼了

本来是在上课,突然想到我好像没把最短路板子过掉,发现是黄,所以就过来水一下。

结果最短路我给写错了、真的是一点面子都不给啊,,,(捂脸

实在看不出来哪错了,所以各位帮忙调一下,谢谢。

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 450010;
const ll INF = 1LL << 50LL;
ll d[N];
int n, m, s, E, head[N], to[N * 2], nxt[N * 2], w[N * 2];
struct node
{
	ll dis; int u;
	const bool operator < (const node &cmp) const { return dis > cmp.dis; }
};
void add(int a, int b, int c) { to[E] = b, w[E] = c, nxt[E] = head[a], head[a] = E++; }
void dijkstra(int s)
{
	for (int i = 1; i <= n; i++) d[i] = INF;
	priority_queue<node> q;
	q.push({0, s}), d[s] = 0;
	while (!q.empty())
	{
		node f = q.top(); q.pop();
		int u = f.u;
		if (f.dis > d[u]) continue;
		for (int i = head[u]; i != -1; i = nxt[i])
		{
			int v = to[i];
			if (d[u] + w[i] < d[v]) d[v] = d[u] + w[i], q.push({d[v], v});
		}
	}
}

int main()
{
	map<pair<int, int>, int> mp; map<pair<int, int>, bool> vis;
	memset(head, -1, sizeof(head)), scanf("%d%d%d", &n, &m, &s);
	for (int i = 0, x, y, z; i < m; i++)
	{
		scanf("%d%d%d", &x, &y, &z);
		if (!vis[{x, y}]) mp[{x, y}] = z, vis[{x, y}] = 1;
		else mp[{x, y}] = min(mp[{x, y}], z);
	}
	for (auto it : mp) add(it.first.first, it.first.second, it.second);
	dijkstra(s);
	for (int i = 1; i <= n; i++) printf("%lld ", d[i]);
	printf("\n");
	return 0;
}
2024/3/3 13:14
加载中...