C++ – Dijskra原理 模板

原理

https://blog.csdn.net/alexfaker/article/details/90199074

模板

https://www.cnblogs.com/iloveori/p/12526461.html#%E8%A7%82%E5%89%8D%E6%8F%90%E7%A4%BA%EF%BC%9A%E8%AF%B7%E4%B8%8D%E8%A6%81%E5%9C%A8%E8%B4%9F%E6%9D%83%E5%9B%BE%E4%B8%AD%E7%86%9F%E7%BB%83%E7%9A%84%E8%BF%90%E7%94%A8%E8%BF%99%E4%B8%AA%E7%AE%97%E6%B3%95%E3%80%82

个人模板

https://www.luogu.com.cn/problem/P4779

#include<iostream>
#include<queue>
#include<cstdio>
#include<cstring>
#include<vector>
#include<algorithm>
#include<utility>
#define go(a,b,c) for(int a=b;a<=c;a++)
using namespace std;
int n, m, s, u, v, w, vis[100010], dis[100010];
struct ed {
    int v, w;
};
vector<ed> vec[100010];
priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > q;
void dij(int x) {
    dis[x] = 0;
    q.push({ 0,x });
    while (!q.empty()) {
        pair<int, int> head = q.top();
        q.pop();
        if (vis[head.second])
            continue;
        vis[head.second] = 1;
        int len = vec[head.second].size();
        go(i, 0, len - 1) {
            if (dis[vec[head.second][i].v] > dis[head.second] + vec[head.second][i].w) {
                dis[vec[head.second][i].v] = dis[head.second] + vec[head.second][i].w;
                q.push({ dis[vec[head.second][i].v],vec[head.second][i].v });
            }
        }
    }
}
int main() {
    cin >> n >> m >> s;
    memset(dis, 0x7f, sizeof dis);
    go(i, 1, m) {
        int x, y, z;
        ed tmp;
        cin >> x >> y >> z;
        tmp.v = y;
        tmp.w = z;
        vec[x].push_back(tmp);
    }
    dij(s);
    go(i, 1, n)
        cout << dis[i] << ' ';
    return 0;
}