Acwing 342题解
代码实现
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+5;
typedef long long ll;
#define max(a,b) (a>=b?a:b)
#define min(a,b) (a>=b?b:a)
typedef pair<int,int> pii;
struct node{ //link-table
int ver,w,next;
}edge[maxn];
int head[maxn],tot;
void add(int u,int v,int w){
edge[++tot].next=head[u]; edge[tot].ver=v;
edge[tot].w=w; head[u]=tot;
}
int cnt,pre[maxn];//link-block
void dfs(int x){
pre[x]=cnt ;
for(int i=head[x];i;i=edge[i].next){
int v=edge[i].ver;
if(!pre[v]){
dfs(v);
}
} return ;
}
int deg[maxn],T,R,P,S;//main-data
int vis[maxn],dist[maxn];//
void solve(int s){
queue<int> q;
for(int i=1;i<=cnt;i++){ //point of in-degee=0
if(deg[i]==0) q.push(i);
}
memset(dist,0x3f,sizeof(dist));
dist[s]=0;//init dist
while(q.size()){ //topo sort
int x=q.front(); q.pop();
priority_queue<pii> pq;
for(int i=1;i<=T;i++){
if(pre[i]==x)
pq.push(make_pair(-dist[i],i) ) ;
}
while(pq.size()){
int nx=pq.top().second; pq.pop();
if(!vis[nx]){
vis[nx]=1;
for(int i=head[nx];i;i=edge[i].next){
int v=edge[i].ver,w=edge[i].w;
if(dist[v]>dist[nx]+w){
dist[v]=dist[nx]+w;
if(pre[nx]==pre[v])//in a same block
pq.push(make_pair(-dist[v],v));
}
if(pre[nx]!=pre[v]){
deg[pre[v]]--;
if(deg[pre[v]]==0)
q.push(pre[v]) ;
}
}
}
}
}
}
int main(){
ios::sync_with_stdio(false); cin.tie(0);cout.tie(0);
cin>>T>>R>>P>>S;
while(R--){
int a,b,c;
cin>>a>>b>>c;
add(a,b,c);//road
add(b,a,c);
}
for(int i=1;i<=T;i++){ //divide block
if(!pre[i]){
cnt++;
dfs(i);
}
}
while(P--){
int a,b,c;
cin>>a>>b>>c; //channel
add(a,b,c);
deg[pre[b]]++;
}
solve(S);//function
for(int i=1;i<=T;i++){ //print ans
if(dist[i]>1e9) cout<<"NO PATH\n";
else cout<<dist[i]<<endl;
}
return 0;
}