道路和航线

一本通·提高篇 · 代码 · cpp · 难度 5/5 · 共 3068 字
道路缩块后按拓扑序块内跑Dijkstra
一本通
练习
正文

// 原题：https://oj.yecheng.tv/p/T1503
// 题意：T 个点，R 条双向非负道路、P 条单向可为负的航线，求 S 到每个点的最短花费，不可达输出 NO PATH。
// 思路：道路把点划分成若干连通块，航线在块之间构成 DAG，按块的拓扑序依次处理，块内用堆优化 Dijkstra，块间用航线松弛并递减入度。
// 复杂度：O((R+P) log T) 时间 / O(T+R+P) 空间
// 易错点：航线保证不会形成回路，所以必须按拓扑序推进而不能直接用普通 Dijkstra；块内堆的初值要包含所有已被航线更新过的点。
#include <bits/stdc++.h>
using namespace std;
const int MAXT = 25005;
const long long INF = (1LL << 60);
struct Edge{
    int to, w;
};
vector<Edge> road[MAXT];
vector<Edge> air[MAXT];
vector<int> block[MAXT];
int bel[MAXT];
int deg[MAXT];
long long dista[MAXT];
int main(){
    int T, R, P, S;
    if(!(cin >> T >> R >> P >> S)) return 0;
    for(int i = 0; i < R; i++){
        int a, b, c;
        cin >> a >> b >> c;
        road[a].push_back({b, c});
        road[b].push_back({a, c});
    }
    for(int i = 0; i < P; i++){
        int a, b, c;
        cin >> a >> b >> c;
        air[a].push_back({b, c});
    }
    int bcnt = 0;
    for(int i = 1; i <= T; i++){
        if(bel[i]) continue;
        bcnt++;
        stack<int> st;
        st.push(i);
        bel[i] = bcnt;
        while(!st.empty()){
            int u = st.top();
            st.pop();
            block[bcnt].push_back(u);
            for(size_t j = 0; j < road[u].size(); j++){
                int v = road[u][j].to;
                if(!bel[v]){
                    bel[v] = bcnt;
                    st.push(v);
                }
            }
        }
    }
    for(int u = 1; u <= T; u++){
        for(size_t j = 0; j < air[u].size(); j++) deg[bel[air[u][j].to]]++;
    }
    for(int i = 1; i <= T; i++) dista[i] = INF;
    dista[S] = 0;
    queue<int> q;
    for(int b = 1; b <= bcnt; b++){
        if(deg[b] == 0) q.push(b);
    }
    while(!q.empty()){
        int b = q.front();
        q.pop();
        priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> pq;
        for(size_t i = 0; i < block[b].size(); i++){
            int v = block[b][i];
            if(dista[v] < INF) pq.push({dista[v], v});
        }
        while(!pq.empty()){
            long long du = pq.top().first;
            int u = pq.top().second;
            pq.pop();
            if(du != dista[u]) continue;
            if(du >= INF / 2) continue;
            for(size_t i = 0; i < road[u].size(); i++){
                int v = road[u][i].to;
                if(du + road[u][i].w < dista[v]){
                    dista[v] = du + road[u][i].w;
                    pq.push({dista[v], v});
                }
            }
        }
        for(size_t i = 0; i < block[b].size(); i++){
            int u = block[b][i];
            for(size_t j = 0; j < air[u].size(); j++){
                int v = air[u][j].to;
                if(dista[u] < INF / 2 && dista[u] + air[u][j].w < dista[v]) dista[v] = dista[u] + air[u][j].w;
                deg[bel[v]]--;
                if(deg[bel[v]] == 0) q.push(bel[v]);
            }
        }
    }
    for(int i = 1; i <= T; i++){
        if(dista[i] >= INF / 2) cout << "NO PATH" << '\n';
        else cout << dista[i] << '\n';
    }
    return 0;
}
道路和航线

正文

一本通·提高篇的其它内容
