记录 dij+拓扑做法

#include<bits/stdc++.h>
using namespace std;
int cnt=0,knt=0,n,m,r,s,dis[25005],ci[25005],head[25005],ru[25005],vis[25005];
vector<int> lis[25005];
struct edge{
int v,w,next;
}e[200005];
void add(int u,int v,int w){
e[++cnt].v=v,e[cnt].w=w,e[cnt].next=head[u],head[u]=cnt;
} 
void dfs(int be,int x){
ci[x]=be;
lis[be].push_back(x);
for(int i=head[x];i;i=e[i].next) if(!ci[e[i].v]) dfs(be,e[i].v);
}

int main(){
memset(dis,0x3f,sizeof(dis));
scanf("%d%d%d%d",&n,&m,&r,&s);
for(int i=1,a,b,c;i<=m;i++){
scanf("%d%d%d",&a,&b,&c);
add(a,b,c),add(b,a,c);
}
memset(ci,0,sizeof(ci));
memset(ru,0,sizeof(ru));
for(int i=1;i<=n;i++) if(!ci[i]) dfs(++knt,i);

for(int i=1,a,b,c;i<=r;i++){
scanf("%d%d%d",&a,&b,&c);
add(a,b,c);
ru[ci[b]]++;
}
queue<int> q;
priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > > qq;
dis[s]=0;
for(int i=1;i<=knt;i++) if(!ru[i]) q.push(i);
while(!q.empty()){
int x=q.front();
q.pop();
for(int i=0;i<lis[x].size();i++)qq.push({dis[lis[x][i]],lis[x][i]});
while(!qq.empty()){
int y=qq.top().second;
qq.pop();
if(vis[y]) continue;
vis[y]=1;
for(int i=head[y];i;i=e[i].next){
if(dis[e[i].v]>dis[y]+e[i].w){
dis[e[i].v]=dis[y]+e[i].w;
if(ci[y]==ci[e[i].v]) qq.push({dis[e[i].v],e[i].v});
}if((ci[y]!=ci[e[i].v])&&(--ru[ci[e[i].v]]==0)) q.push(ci[e[i].v]);}}}
for(int i=1;i<=n;i++){
if(dis[i]>=0x3f3f3f3f)printf("NO PATH\n");
else printf("%d\n",dis[i]);
}

return 0;
}