做成五颜六色了......

P4779 【模板】单源最短路径(标准版)

bei_awa @ 2023-07-22 10:38:26

#include <queue>
#include <math.h>
#include <stack>
#include <stdio.h>
#include <iostream>
#include <vector>
#include <iomanip>
#include <string.h>
#include <algorithm>
using namespace std;
#define int long long
const int N = 1e5 + 10;
const int INF = 0x3f3f3f3f;
int n , m  , s , id;
int head[N] , to[N] , w[N] , ne[N];
void add(int x, int y , int z)
{
    id++;
    w[id] = z;
    to[id] = y;
    ne[id] = head[x];
    head[x] = id;
}
struct node
{
    int num,id;
    bool operator < (const node& a)const 
    {
        return num > a.num;
    }
};
int dis[N] , vis[N];
void dijkstra()
{
    for(int i = 1; i <= n ; i++)
        dis[i] = 2147483647;
    memset(vis,0,sizeof vis);
    priority_queue<node> p;
    dis[s] = 0;
    p.push((node){0,s});
    while(!p.empty())
    {
        node t= p.top();
        p.pop();
        if(vis[t.id] || t.num != dis[t.id]) 
            continue;
        int idx = t.id;
        vis[idx] = 1;
        for(int j = head[idx] ; j ; j = ne[j])
        {
            int v = to[j];
            if(!vis[v] && dis[v] > t.num + w[j])
            {
                dis[v] = t.num + w[j];
                p.push( (node){dis[v] , v} );
            }
        }

    }

}
signed main()
{
    cin >> n >> m >> s;
    for(int i = 1 ,x,y,z; i <= m ; i++)
    {
        scanf("%lld%lld%lld",&x,&y,&z);
        add(x,y,z);
    }
    dijkstra();
    for(int i = 1; i <= n ; i++)
        printf("%lld ",dis[i]);
    return 0;
}

求大佬指点


by Ayano_Kimishima @ 2023-07-22 10:45:19

666


by hjqhs @ 2023-07-22 10:46:55

@bei_awa 你不是 AC 了吗


by bei_awa @ 2023-07-22 10:49:01

@hjqhs 这是另一种做法,但这种没做对


|