本文共 1444 字，大约阅读时间需要 4 分钟。
拓扑排序，然后从终点开始递推。
#pragma comment(linker, "/STACK:1024000000,1024000000")#include #include #include #include #include #include #include #include #include #include #include using namespace std;typedef long long LL;const double pi=acos(-1.0);void File(){ freopen("D:\\in.txt","r",stdin); freopen("D:\\out.txt","w",stdout);}const int INF=0x7FFFFFFF;int T,n,m;struct Edge { int u,v,w,nx; } e[100010];int sz,h[10010],r[10010];struct X { int order,id; } p[10010];int dis[10010][2];void add(int a,int b,int c){ e[sz].u=a; e[sz].v=b; e[sz].w=c; e[sz].nx=h[a]; h[a]=sz++;}bool cmp(X a,X b){ return a.order>b.order; }bool top(){ queue Q; sz=0; for(int i=0;i =1;i--) { int id=p[i].id; if(id==n-1) { dis[id][1]=dis[id][0]=0; continue;} for(int j=h[id];j!=-1;j=e[j].nx) { if(dis[e[j].v][0]==INF) continue; dis[id][0]=min(dis[id][0],dis[e[j].v][0]+e[j].w); } int x1=INF,x2=INF; for(int j=h[id];j!=-1;j=e[j].nx) { if(dis[e[j].v][1]==INF) continue; x1=min(x1,dis[e[j].v][1]+e[j].w); } bool flag=0; for(int j=h[id];j!=-1;j=e[j].nx) { if(dis[e[j].v][0]==INF) continue; if(flag==0&&dis[e[j].v][0]+e[j].w==dis[id][0]) { flag=1; continue; } x2=min(x2,dis[e[j].v][0]+e[j].w); } dis[id][1]=max(x1,x2); } if(dis[0][1]==INF||dis[0][0]==INF) printf("-1\n"); else printf("%d\n",dis[0][1]); } return 0;}
转载于:https://www.cnblogs.com/zufezzt/p/5782060.html