洛谷 P3008. Roads and Planes G

题目描述

link

分析

题意：$T$ 个城镇由 $R$ 条双向道路（边权非负）和 $P$ 条单向航线（边权可为负）相连，求从起点 $S$ 到所有城镇的最短路，不可达的输出 NO PATH。

难点：图中存在负权边，Dijkstra 的贪心会失效；而 SPFA 在本题的数据规模下会被卡。题目给出了一个关键保证：如果存在航线 $a\to b$，那么不可能通过道路和航线从 $b$ 回到 $a$。这意味着图中以航线相连的点之间没有负环（不保证道路相连的点之间没有负环）；并且把"只用道路相连"的点缩成一个连通块后，航线只出现在块与块之间，块之间的航线图是一个有向无环图（DAG）。

思路：连通块 + 拓扑排序 + 块内 Dijkstra

既然航线图是 DAG，就可以借助拓扑序把问题"分而治之"：

1. 划分连通块：只加双向道路，用 DFS 求出每个点所在的连通块编号 $c[i]$，并记录每个块包含哪些点。

2. 建 DAG：加回单向航线，统计每个块的入度——航线 $x\to y$ 使块 $c[y]$ 的入度加 $1$。

3. 拓扑序 + 块内 Dijkstra：入度为 $0$ 的块先入队。处理块 $id$ 时，把块内所有点放进堆里跑 Dijkstra：

   • 块内边全是非负权道路，Dijkstra 的贪心成立；
   • 松弛到同块的点 $j$ 时，更新后正常入堆；
   • 遇到指向其他块的点 $j$ 的边时，若更优则更新 $\mathrm{dist}[j]$，但不入堆；同时把块 $c[j]$ 的入度减 $1$。由于每个点只会出堆一次，每条航线恰好被处理一次，入度减到 $0$ 的块就可以入拓扑队列。

   这样保证：处理某个块时，所有指向它的航线产生的松弛都已完成，之后不会被更小的值再次更新，因此每个点出队时 $\mathrm{dist}$ 就是最终最短路。

4. 判断不可达：负权航线可能把初始的 $+\mathrm{\infty }$ 更新成略小的值，所以不能仅凭 $\mathrm{dist}[i]$ 是否仍等于初始值来判断，而应检查 $\mathrm{dist}[i]>\mathrm{INF}/2$，满足则输出 NO PATH。

正确性：块内 Dijkstra 处理非负道路，块间拓扑序保证负权航线的松弛按依赖顺序进行，两者结合即为全局最短路。

复杂度：每条边至多被松弛一次，总复杂度 $O((T+R+P)\log T)$。

参考代码

#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> PII;

const int N = 25010, M = 150010;
int h[N], e[M], w[M], ne[M], idx;
int c[N], deg[N];
vector<int> b[N];
int bs; // 连通块的数量
int dist[N];
bool st[N];
int t, r, p, s;

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

void dfs(int start, int id) {
    c[start] = id;
    b[id].push_back(start);
    for (int i = h[start]; i != -1; i = ne[i]) {
        int j = e[i];
        if (c[j]) continue;
        dfs(j, id);
    }
}

void dijkstra(int id, queue<int>& q) {
    priority_queue<PII, vector<PII>, greater<PII>> heap;

    for (auto x : b[id]) {
        heap.push({dist[x], x});
    }

    while (heap.size()) {
        auto k = heap.top();
        heap.pop();

        if (st[k.second]) continue;
        st[k.second] = 1;

        for (int i = h[k.second]; i != -1; i = ne[i]) {
            int j = e[i];
            if (dist[j] > k.first + w[i]) {
                dist[j] = k.first + w[i];
                if (c[k.second] == c[j]) heap.push({dist[j], j});
            }
            if (c[k.second] != c[j]) {
                deg[c[j]] -= 1;
                if (deg[c[j]] == 0) {
                    q.push(c[j]);
                }
            }
        }
    }
}

int main() {
    memset(h, -1, sizeof h);

    cin >> t >> r >> p >> s;
    for (int i = 0; i < r; i++) {
        int a, b, c; cin >> a >> b >> c;
        add(a, b, c); add(b, a, c);
    }

    for (int i = 1; i <= t; i++) {
        if (!c[i]) {
            bs++;
            dfs(i, bs);
        }
    }

    for (int i = 0; i < p; i++) {
        int x, y, z; cin >> x >> y >> z;
        add(x, y, z);
        deg[c[y]]++;
    }

    // topsort
    memset(dist, 0x3f, sizeof dist);
    dist[s] = 0;

    queue<int> q;
    for (int i = 1; i <= bs; i++) {
        if (!deg[i]) q.push(i);
    }

    while (q.size()) {
        int k = q.front();
        q.pop();

        dijkstra(k, q);
    }

    for (int i = 1; i <= t; i ++ ) {
        if (dist[i] > 0x3f3f3f3f / 2) cout << "NO PATH" << endl;
        else cout << dist[i] << endl;
    }

    return 0;
}