欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

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

程序员文章站 2022-07-05 11:12:19
题意 。。。求最短路 Sol 前几天写dijkstra的时候没打vis标记居然A了,然后天真的我就以为Dijkstra不用打标记。 事实上dijkstra真的不用打标记,只不过会被卡成SPFA的复杂度 ......

题意

。。。求最短路

Sol

前几天写dijkstra的时候没打vis标记居然A了,然后天真的我就以为Dijkstra不用打标记。

事实上dijkstra真的不用打标记,只不过会被卡成SPFA的复杂度

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<ext/pb_ds/priority_queue.hpp>
#define MP(x, y) make_pair(x, y)
#define Pair pair<int, int> 
using namespace std;
const int MAXN = 1e6 + 10, INF = 2147483646, B = 19;
inline int read() {
    char c = getchar(); int x = 0, f = 1;
    while(c < '0' || c > '9') {if(c == '-') f = 1; c = getchar();}
    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * f;
}
int N, M, S;
struct Edge {
    int u, v, w, nxt;
}E[MAXN];
int head[MAXN], num = 1;
void AddEdge(int x, int y, int z) {
    E[num] = (Edge) {x, y, z, head[x]};
    head[x] = num++;
}
int dis[MAXN], vis[MAXN];
priority_queue<Pair> q; 
void Dij() {
    for(int i = 1; i <= N; i++) dis[i] = 2147483647;
    dis[S] = 0; q.push(MP(0, S));
    while(!q.empty()) {
        int p = q.top().second; q.pop();
        if(vis[p]) continue; vis[p] = 1;
        for(int i = head[p]; i != -1; i = E[i].nxt) {
            int to = E[i].v;
            if(dis[to] > dis[p] + E[i].w) 
                dis[to] = dis[p] + E[i].w,
                q.push(MP(-dis[to], to));
        }
    }
    for(int i = 1; i <= N; i++)
        printf("%d ", dis[i]);
}
main() {
    memset(head, -1, sizeof(head));
    N = read(); M = read(); S = read();
    for(int i = 1; i <= M; i++) {
        int x = read(), y = read(), z = read();
        AddEdge(x, y, z);
    }
    Dij();
    return 0;
}