首页 > > 程序设计 > C/C++ >

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

2018-07-24 07:50:55来源：博客园阅读 ()

题意

。。。求最短路

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;
}