求助单源最短路dijkstra
查看原帖
求助单源最短路dijkstra
532029
Blind_Swallow楼主2023/2/25 13:26

求助一道模板题,和洛谷的不一样,题目如下

【题目描述】

给定一个 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;
}
2023/2/25 13:26
加载中...