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;
}