道路与航线

AcWing-342-道路与航线

分析

见《进阶指南》第357页。

实现

#include <iostream>
#include <cstring>
#include <queue>
using namespace std;

const int N = 25010, M = 150010;
struct edge {
    int to, next, w;
};
edge e[M];
int idx, head[N], in_deg[N];
struct node {
    int idx, dis;
    bool operator < (const node& o) const {
        return dis > o.dis;
    }
};
int n, r, p, s;
int tot, c[N];
int dis[N];
bool mark[N];

void add_edge (int u, int v, int w) {
    e[idx].w = w;
    e[idx].to = v;
    e[idx].next = head[u];
    head[u] = idx ++;
}
void dfs (int cur) {
    for (int i = head[cur]; i != -1; i = e[i].next) {
        int to = e[i].to;
        if (c[to] == 0) {
            c[to] = tot;
            dfs(to);
        }
    }
}
void topo_sort () {
    memset(dis, 0x3f, sizeof(dis));
    dis[s] = 0;
    queue<int> q;
    for (int i = 1; i <= tot; ++ i)
        if (in_deg[i] == 0)
            q.push(i);
    while (!q.empty()) {
        int cur = q.front();
        q.pop();
        priority_queue<node> pq;
        for (int i = 1; i <= n; ++ i)
            if (c[i] == cur)
                pq.push({ i, dis[i] });
        while (!pq.empty()) {
            int cur = pq.top().idx;
            pq.pop();
            if (mark[cur] == true) continue;
            mark[cur] = true;
            for (int i = head[cur]; i != -1; i = e[i].next) {
                int to = e[i].to, w = e[i].w;
                if (dis[cur] + w < dis[to]) {
                    dis[to] = dis[cur] + w;
                    if (c[to] == c[cur])
                        pq.push({ to, dis[to] });
                }
                if (c[to] != c[cur] && (-- in_deg[c[to]] == 0))
                    q.push(c[to]);
            }
        }
    }
}

int main () {
    memset(head, -1, sizeof(head));
    cin >> n >> r >> p >> s;
    for (int i = 1, u, v, w; i <= r; ++ i) {
        cin >> u >> v >> w;
        add_edge(u, v, w);
        add_edge(v, u, w);
    }

    for (int i = 1; i <= n; ++ i) {
        if (c[i] == 0) {
            c[i] = ++ tot;
            dfs(i);
        }
    }
    for (int i = 1, u, v, w; i <= p; ++ i) {
        cin >> u >> v >> w;
        add_edge(u, v, w);
        ++ in_deg[c[v]];
    }
    topo_sort();
    for (int i = 1; i <= n; ++ i) {
        if (dis[i] > 1e9) { // 负权边
            cout << "NO PATH" << endl;
        } else {
            cout << dis[i] << endl;
        }
    }
    return 0;
}