基于链式前向星的堆优化dijsktra | 模板

关于SPFA，ta死了

基于链式前向星的堆优化\(dijsktra\):

复杂度\(O(mlogn)\)，要求非负权。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<vector>

#define ll long long

const int maxn = 5e5 + 10;
const int inf = 2147483647;
int head[maxn << 1], to[maxn << 1], nxt[maxn << 1], val[maxn << 1], cnt;
ll dis[maxn];
bool vis[maxn];
int n, m, s;

inline void add(int a, int b, int c) {
    to[++cnt] = b;
    val[cnt] = c;
    nxt[cnt] = head[a];
    head[a] = cnt;
}

inline void init() {
    for (int i = 1; i <= n; i++) dis[i] = inf;
    dis[s] = 0;
}

inline void dijsktra() {
    init();
    std::priority_queue<std::pair<int, int>, std::vector<std::pair<int, int> >, std::greater<std::pair<int, int> > > q;
    q.push(std::make_pair(0, s));
    while (!q.empty()) {
        int u = q.top().second;
        q.pop();
        for (int i = head[u]; i; i = nxt[i]) {
            int v = to[i];
            if (vis[v]) continue;
            if (dis[v] > dis[u] + val[i]) {
                dis[v] = dis[u] + val[i];
                q.push(std::make_pair(dis[v], v));
            }
        }

    }
    return;
}

int main() {
    scanf("%d%d%d", &n, &m, &s);
    while (m--) {
        int u, v, w;
        scanf("%d%d%d", &u, &v, &w);
        add(u, v, w);
    }
    dijsktra();
    for (int i = 1; i <= n; i++)
        printf("%lld ", dis[i]);
    return 0;
}

原文地址：http://www.cnblogs.com/MrWangnacl/p/16814769.html