记录编号	577231	评测结果	AAAAAAAAAAAAAAAA
题目名称	[USACO Jan11]道路与航线	最终得分	100
用户昵称	lihaoze	是否通过	通过
代码语言	C++	运行时间	0.778 s
提交时间	2022-10-27 17:56:15	内存使用	10.81 MiB

#include "bits/stdc++.h"

using PII = std::pair<int, int>;

const int N = 2e5 + 10;
int n, r, p, s, cnt;
int id[N], dist[N];
int e[N], ne[N], w[N], h[N], idx;
std::vector<int> points[N];
std::map<int, bool> st;

void add(int a, int b, int c) {
    e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx ++;
}

void dfs(int u) {
    for (int i = h[u]; i != -1; i = ne[i]) {
        int v = e[i];
        if (!id[v]) {
            id[v] = id[u];
            dfs(v);
        }
    }
}

int ind[N];
void toposort() {
    std::queue<int> q;
    dist[s] = 0, q.push(id[s]);
    for (int i = 1; i <= cnt; ++ i) {
        if (ind[i] == 0 && i != id[s]) {
            q.push(i);
        }
    }
    while (q.size()) {
        int t = q.front(); q.pop();
        std::priority_queue<PII, std::vector<PII>, std::greater<PII>> heap;
        for (auto i : points[t]) {
            heap.push({ dist[i], i });
        }
        while (heap.size()) {
            auto [_, u] = heap.top(); heap.pop();
            if (st[u]) continue;
            st[u] = true;
            for (int i = h[u]; i != -1; i = ne[i]) {
                int v = e[i];
                if (dist[u] != 0x3f3f3f3f && dist[u] + w[i] < dist[v]) {
                    dist[v] = dist[u] + w[i];
                    if (id[u] == id[v]) heap.push({ dist[v], v });
                }
                if (id[u] != id[v]) {
                    if (-- ind[id[v]] == 0) q.push(id[v]);
                }
            }
        }
    }
}

int main() {
    freopen("roadplane.in", "r", stdin); 
    freopen("roadplane.out", "w", stdout);
    memset(h, -1, sizeof h);
    memset(dist, 0x3f, sizeof dist);
    std::cin >> n >> r >> p >> s;
    for (int i = 1; i <= r; ++ i) {
        int a, b, c;
        std::cin >> a >> b >> c;
        add(a, b, c), add(b, a, c);
    }
    for (int i = 1; i <= n; ++ i) {
        if (!id[i]) {
            id[i] = ++ cnt;
            dfs(i);
        }
    }
    for (int i = 1; i <= n; ++ i) {
        points[id[i]].emplace_back(i);
    }
    for (int i = 1; i <= p; ++ i) {
        int a, b, c;
        std::cin >> a >> b >> c;
        add(a, b, c), ++ ind[id[b]];
    }
    toposort();
    for (int i = 1; i <= n; ++ i) {
        if (dist[i] == 0x3f3f3f3f) {
            std::cout << "NO PATH" << '\n';
        } else {
            std::cout << dist[i] << '\n';
        }
    }
    return 0;
}