链式前向星板子 RE 求调

喵仔牛奶 @ 2023-12-16 19:51:09

by 喵仔牛奶 @ 2023-12-16 19:51:27

// writer: Milkcat
// time: 
#include <bits/stdc++.h>
#define REP(i, l, r) for (int i = (l); i <= (r); ++ i)
#define DEP(i, r, l) for (int i = (r); i >= (l); -- i)
#define fi first
#define se second
#define pb push_back
using namespace std;
namespace Milkcat {
    typedef long long LL;
    typedef pair<LL, LL> pii;
    const int N = 1e6 + 5;
    struct Graph {
        struct edge { int from, to, next; LL w; }; int n; vector<edge> e; vector<int> h;
        void resize(int n) { h.resize(n + 1, -1); } Graph(int n = 0) { resize(n); }
        void chk(int u) { if (u > n) n = u, h.resize(n + 1, -1); }
        void ins(int u, int v, LL w = 0) { chk(max(u, v)), e.pb({u, v, h[u], w}), h[u] = e.size() - 1; }
        void twi(int u, int v, LL w = 0) { ins(u, v, w), ins(v, u, w); }
        void clear() { e.clear(), h.clear(); }
        #define FEG(u, v, W, G, i) \
            for (LL i = G.h[u], v = G.e[i].to, W = G.e[i].w; ~i; i = G.e[i].next, v = G.e[i].to, W = G.e[i].w)
    } G;
    vector<LL> Dijk(const Graph& G, int s) {
        vector<LL> dis(G.n + 1, 1e18), vis(G.n + 1);
        priority_queue<pii, vector<pii>, greater<pii>> q;
        q.push(pii(0, s)), dis[s] = 0;
        while (!q.empty()) {
            int u = q.top().se; q.pop();
            if (vis[u]) continue;
            vis[u] = 1;
            FEG(u, v, w, G, i)
                if (dis[v] > dis[u] + w) {
                    dis[v] = dis[u] + w;
                    if (!vis[v]) q.push(pii(dis[v], v));
                }
        }
        return dis;
    }
    int n, m, u, v, w, s;
    int main() {
        cin >> n >> m >> s;
        REP(i, 1, m)
            cin >> u >> v >> w, G.ins(u, v, w);
        auto dis = Dijk(G, s);
        REP(i, 1, n) cout << dis[i] << ' ';
        cout << '\n';
        return 0;
    }
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int T = 1;
    while (T --) Milkcat::main();
    return 0;
}