0分求条

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

EternityForMe @ 2024-12-23 16:12:45

#include<bits/stdc++.h>
#define ll long long
const int N=1e5+5,M=4e5+5;
using namespace std;
int inf=(1<<31)-1;
int head[N], cnt;
int v, e, x, y, z, s;
int dis[N], vis[N];
struct Eade {
    int next, to, dis;
} eade[M];
void addEade(int from, int to, int dis) {
    eade[++cnt].next = head[from];
    eade[cnt].to = to;
    eade[cnt].dis = dis;
    head[from] = cnt;
}
void dejkstra(int s) {
    ll dis[100005],vis[100005]={0};
    memset(dis,0x3f,sizeof(dis));
    priority_queue<pair<int ,int>>q;
    while(q.size()){
        int x=q.top().second;
        q.pop();
        if(vis[x])continue;
        vis[x]=1;
        for (ll i = head[x]; i; i = eade[i].next) {
            int y = eade[i].to;
            int d = eade[i].dis;
            if (dis[y] > dis[x] + d) {
                dis[y] = dis[x] + d;
                q.push(make_pair(-dis[y],y));
            }
        }
    }
    for (ll i = 1; i <= v; i++) {
        if(dis[i]>inf) cout<<inf<<' ';
        else cout << dis[i] << ' ';
    }
}
int main() {
    cin >> v >> e >> s;
    for (ll i = 1; i <= e; i++) {
        cin >> x >> y >> z;
        addEade(x, y, z);
    }
    dejkstra(s);
    return 0;
}

|