题目链接:
http://www.lydsy.com/JudgeOnline/problem.php?id=2200
有负权边,所以不能直接dijkstra。。而spfa已经死了。。。
但是题目保证“航线”不会出现在环里,所以如果把“道路”联结的点都缩起来就会变成一个DAG。。。
考虑一个只由道路联结的块,此时可以直接dijkstra。。。
DAG上就可以用拓扑排序的方法排除负权的影响,然后就没有然后了。。
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<queue> #include<vector> #include<map> #define pa pair<int,int> #define LL long long using namespace std; inline int read(){ int x=0,f=1;char ch=getchar(); while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();} while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();} return x*f; } inline void Out(int a){ if(a>9) Out(a/10); putchar(a%10+‘0‘); } const int inf=1e9+10; const LL mod=1e9+7; const int N=2e5+50; int n,m1,m2,S,cnt,CNT,blo; int hed[N],HED[N],dis[N],bel[N],du[N]; struct edge{ int r,nxt,val; }e[N]; void insert(int u,int v,int w){ e[++cnt].r=v;e[cnt].nxt=hed[u];hed[u]=cnt;e[cnt].val=w; } struct EDGE{ int r,nxt,val; }E[N]; void INSERT(int u,int v,int w){ E[++CNT].r=v;E[CNT].nxt=HED[u];HED[u]=CNT;E[CNT].val=w; } int q[N]; priority_queue< pa ,vector< pa >,greater< pa > >PQ; bool vis[N]; vector<int> ve[N]; void dfs(int x,int c){ bel[x]=c; ve[c].push_back(x); for(int i=hed[x];i;i=e[i].nxt) if(!bel[e[i].r]) dfs(e[i].r,c); } int main(){ n=read();m1=read();m2=read();S=read(); for(int i=1;i<=n;++i) dis[i]=inf; int u,v,w; for(int i=1;i<=m1;++i){ u=read();v=read();w=read(); insert(u,v,w); insert(v,u,w); } for(int i=1;i<=m2;++i){ u=read();v=read();w=read(); INSERT(u,v,w); } for(int i=1;i<=n;++i) if(!bel[i]) dfs(i,++blo); for(int i=1;i<=n;++i) for(int j=HED[i];j;j=E[j].nxt) ++du[bel[E[j].r]]; int l=1,r=0,x; for(int i=1;i<=blo;++i) if(!du[i]) q[++r]=i; dis[S]=0; while(l<=r){ x=q[l++]; for(int i=0;i<ve[x].size();++i){ if(dis[ve[x][i]]<inf) PQ.push(make_pair(dis[ve[x][i]],ve[x][i])); } while(!PQ.empty()){ u=PQ.top().second; w=PQ.top().first; PQ.pop(); if(vis[u])continue; else vis[u]=1; for(int i=hed[u];i;i=e[i].nxt) if(dis[e[i].r]>dis[u]+e[i].val){ dis[e[i].r]=dis[u]+e[i].val; PQ.push(make_pair(dis[e[i].r],e[i].r)); } for(int i=HED[u];i;i=E[i].nxt) if(dis[E[i].r]>dis[u]+E[i].val) dis[E[i].r]=dis[u]+E[i].val; } for(int i=0;i<ve[x].size();++i){ for(int j=HED[ve[x][i]];j;j=E[j].nxt){ --du[bel[E[j].r]]; if(!du[bel[E[j].r]]) q[++r]=bel[E[j].r]; } } } for(int i=1;i<=n;++i){ if(dis[i]==inf) printf("NO PATH\n"); else printf("%d\n",dis[i]); } return 0; }
This passage is made by Iscream-2001.
BZOJ 2200--[Usaco2011 Jan]道路和航线(最短路&拓扑排序)
原文:https://www.cnblogs.com/Yuigahama/p/9671244.html