P3008 [USACO11JAN] Roads and Planes G

P3008

连通块统计后，形成DAG

核心解法

解法深研思未休，
图论算法解绸缪。
负权路径何所惧，
拓扑排序定风流。 

/*
解法深研思未休，
图论算法解绸缪。
负权路径何所惧，
拓扑排序定风流。
*/
#include<bits/stdc++.h>
using namespace std;
int INF = 1e9+7; 
int n,r,p,s;
int d[100100];//所属连通块
int dis[100010];
bool vis[100010];
queue<int> t;//拓扑排序 
vector<int> block[25010];//连通块点集 
int pd[100100];//是否为顶点； 
int in[100100],tot;
struct ede{int v,w;bool operator <(const ede a)const{return w > a.w;}
};
vector<ede> g[100010];
void dfs(int u,int t) {//染色 if(d[u])return;d[u] = t; block[t].push_back(u);for(ede vis:g[u]){int v = vis.v;dfs(v,t);}
}
void dijk(int s){//对连通块 S 进行dijkpriority_queue<ede> q;for(int v:block[s]){if(pd[v]){//  cout<<" "<<v<<" "<<dis[v]<<endl;q.push({v,dis[v]});}}while(!q.empty()){ede tp = q.top();q.pop();int u = tp.v;if(vis[u])continue;vis[u] = 1;//cout<<u<<endl;for(ede vised:g[u]){int v = vised.v,w = vised.w;//cout<<u<<" "<<v<<" "<<w<<endl;if(dis[v] > dis[u]+w){dis[v] = dis[u]+w;if(d[v] == d[u]&&!vis[v]){q.push({v,dis[v]}); }}}}} 
vector<int> b[30001];
void topu(int S){for(int i = 1;i <= tot;i++){if(in[i] == 0)t.push(i);}dis[S] = 0;pd[S] = 1;while(!t.empty()){int u = t.front();t.pop();//cout<<u<<endl;dijk(u);for(int v:b[u]){in[v]--;if(in[v] == 0){t.push(v);}}}
}
int main(){memset(dis,0x3f,sizeof(dis));cin>>n>>r>>p>>s;for(int i = 1;i <= r;i++){int u,v,w;cin>>u>>v>>w;g[u].push_back({v,w});g[v].push_back({u,w});}for(int i = 1;i <= n;i++){if(!d[i]){tot++;dfs(i,tot);}}for(int i = 1;i <= p;i++){int u,v,w;cin>>u>>v>>w;g[u].push_back({v,w});in[d[v]]++;pd[v] = 1;b[d[u]].push_back({d[v]});}topu(s);for(int i = 1;i <= n;i++){if(dis[i] > INF/2){cout<<"NO PATH"<<endl;}else{cout<<dis[i]<<endl;}}
}