求助一道模板题,和洛谷的不一样,题目如下
给定一个 N个点,M条有向边的带非负权图,请你计算从 S出发,到每个点的距离。
第一行为三个正整数N, M, S。 第二行起M行,每行三个非负整数u_i, v_i, w_i,表示从u_i到v_i有一条权值为w_i的边。
输出一行 N 个空格分隔的非负整数,表示 S 到每个点的距离。 (若S=i则最短路径长度为0,若从点S无法到达点i,则最短路径长度为2147483647)
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
int n, m, s;
int fr[100010], to[200010], nex[200010], v[200010], tl, d[100010];
bool vis[100010];
void add(int x, int y, int w)
{
to[++tl] = y;
v[tl] = w;
nex[tl] = fr[x];
fr[x] = tl;
}
struct node
{
int x, key;
bool operator < (const node &b) const
{
return key > b.key;
}
};
priority_queue<node> q;
bool dijkstra()
{
d[s] = 0;
q.push(node{s, 0});
while(!q.empty())
{
int x = q.top().x;
q.pop();
if(vis[x]) continue;
vis[x] = 1;
for(int i = fr[x]; i; i = nex[i])
{
int u = to[i], l = v[i];
if(d[u] > d[x] + l)
{
d[u] = d[x] + l;
q.push(node{u, d[u]});
}
}
}
}
int main()
{
scanf("%d%d%d", &n, &m, &s);
for(int i = 1; i <= m; i++)
{
int x, y, z;
scanf("%d%d%d", &x, &y, &z);
add(x, y, z);
}
for(int i = 1; i <= n; i++)
d[i] = 2147483647;
dijkstra();
for(int i = 1; i <= n; i++)
printf("%d ", d[i]);
return 0;
}