太丢人现眼了
本来是在上课,突然想到我好像没把最短路板子过掉,发现是黄,所以就过来水一下。
结果最短路我给写错了、真的是一点面子都不给啊,,,(捂脸
实在看不出来哪错了,所以各位帮忙调一下,谢谢。
#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;
}