P3008 [USACO11JAN]Roads and Planes G

P3008 [USACO11JAN]Roads and Planes G

思路

按照分连通块的方法进行计算，并且如果不是本连通块的点，不能在现在的本次dfs中求解最小值。要一个一个的联通快进行标记。

/*
不能直接走disj的话，缩点的思想很重要
首先尽量不要使用spfa进行走图，可能会卡
对道路进行求连通块，对航线求度数，然后利用topsort进行求解连通块

一次只对一个集合里面的点进行更新

*/
#include <bits/stdc++.h>
using namespace std;
const int N=25005,inf=2e9;
using pii=pair<int,int>;

vector<pii>v1[N],v2[N];
vector<int>v[N];
int id[N],in[N],dis[N];
bool vis[N];

void dfs(int now,int num) {
    id[now]=num;
    v[num].push_back(now);
    for(auto [to,wi]:v1[now])
        if(id[to]==0)dfs(to,num);
}

int main() {
    int n,m1,m2,st;
    cin>>n>>m1>>m2>>st;
    for(int i=1;i<=m1;i++) {
        int x,y,wi;
        cin>>x>>y>>wi;
        v1[x].push_back({y,wi});
        v1[y].push_back({x,wi});
    }
    for(int i=1;i<=m2;i++) {
        int x,y,wi;
        cin>>x>>y>>wi;
        v2[x].push_back({y,wi});
    }
    int cnt=0;
    for(int i=1;i<=n;i++)if(id[i]==0)dfs(i,++cnt);
    for(int i=1;i<=n;i++) {
        dis[i]=(i==st?0:inf);
        for(auto [to,wi]:v2[i])in[id[to]]++;
    }
    queue<int>q;
    for(int i=1;i<=cnt;i++)
        if(in[i]==0)q.push(i);
    while(!q.empty()) {
        int t=q.front();q.pop();
        priority_queue<pii>pq;
        for(auto to:v[t])if(dis[to]<inf)pq.push({-dis[to],to});
        while(!pq.empty()) {
            auto [w,now]=pq.top();pq.pop();w=-w;
            if(vis[now])continue;vis[now]=1;
            for(auto [to,wi]:v1[now])
                if(dis[to]>w+wi) {
                    dis[to]=w+wi;
                    pq.push({-dis[to],to});
                }
            for(auto [to,wi]:v2[now])
                if(dis[to]>w+wi)dis[to]=w+wi;
        }
        for(auto now:v[t])
            for(auto [to,wi]:v2[now])
                if(--in[id[to]]==0)q.push(id[to]);
                
    }
    for(int i=1;i<=n;i++) {
        if(dis[i]==inf)cout<<"NO PATH\n";
        else cout<<dis[i]<<endl;
    }
    return 0;
}