首页 > 代码库 > BZOJ1880 SDOI2009 Elaxia的路线 最短路+拓扑排序
BZOJ1880 SDOI2009 Elaxia的路线 最短路+拓扑排序
题意：给定两个点对和一张无向图，求两个点对的最短路中，重边边权和的最大值
题解：
首先从给出的四个点出发跑出到其他所有点的最短路，然后判断哪些边是重边。找出所有重边后，将其构有向图，在该图上用拓扑排序求最长路。
开始的时候枚举每一条边我没有建反向边，而是每次判定的时候互换一下边的始末点看是否合法，结果最后一个点死活过不去。后来上网搜题解才知道，必须建反向边，与原边分别判断。果然偷懒就是不行啊……
#include <cstdio>#include <cstring>#include <cstdlib>#include <iostream>#include <algorithm>#include <deque>using namespace std;#define INF 6666666const int MAXN=1500+2;const int MAXM=300000+2;struct Hash{ int u,w; Hash *Next; Hash(){} Hash(int _u,int _w,Hash *_Next):u(_u),w(_w),Next(_Next){}}*Tab[2][MAXN],mem[6*MAXM];int N,M,cnt[2],d[4][MAXN],c[MAXN],X1,Y1,X2,Y2,Ans;bool Flag[MAXN];deque<int> q;void Insert(int t,int u,int v,int w){ Tab[t][u]=&(mem[cnt[t]++]=Hash(v,w,Tab[t][u]));}void SPFA(int s,int *d){ for(int i=1;i<=N;i++) d[i]=INF; d[s]=0,q.push_front(s); int x; while(!q.empty()){ x=q.front(),q.pop_front(); for(Hash *p=Tab[0][x];p;p=p->Next){ if(d[p->u]<=d[x]+p->w) continue; d[p->u]=d[x]+p->w; if(Flag[p->u]) continue; Flag[p->u]=1; if(!q.empty() && d[p->u]<=d[q.front()]) q.push_front(p->u); else q.push_back(p->u); } Flag[x]=0; }}bool Check1(int u,int v,int w){ if(d[0][u]+d[1][v]+w!=d[0][Y1]) return 0; if(d[2][u]+d[3][v]+w!=d[2][Y2]) return 0; return 1;}bool Check2(int u,int v,int w){ if(d[0][u]+d[1][v]+w!=d[0][Y1]) return 0; if(d[2][u]+d[3][v]+w!=d[2][X2]) return 0; return 1;}int Topologic_Sort(){ memset(d[2],0,sizeof(d[0])); for(int i=1;i<=N;i++) if(!c[i]) q.push_back(i); int x; while(!q.empty()){ x=q.front(),q.pop_front(); for(Hash *p=Tab[1][x];p;p=p->Next){ c[p->u]--,d[2][p->u]=max(d[2][p->u],d[2][x]+p->w); if(!c[p->u]) q.push_back(p->u); } } int Ans=-1; for(int i=1;i<=N;i++) Ans=max(Ans,d[2][i]); return Ans;}int main(){ cin >> N >> M >> X1 >> Y1 >> X2 >> Y2; for(int i=1,u,v,w;i<=M;i++){ scanf("%d %d %d",&u,&v,&w); Insert(0,u,v,w),Insert(0,v,u,w); } SPFA(X1,d[0]),SPFA(Y1,d[1]),SPFA(X2,d[2]),SPFA(Y2,d[3]); for(int i=1;i<=N;i++) for(Hash *p=Tab[0][i];p;p=p->Next) if(Check1(i,p->u,p->w)) Insert(1,i,p->u,p->w),c[p->u]++; Ans=Topologic_Sort(); SPFA(Y2,d[2]),SPFA(X2,d[3]); memset(Tab[1],0,sizeof(Tab[1])); for(int i=1;i<=N;i++) for(Hash *p=Tab[0][i];p;p=p->Next) if(Check2(i,p->u,p->w)) Insert(1,i,p->u,p->w),c[p->u]++; cout << max(Ans,Topologic_Sort()) << endl; return 0;}
BZOJ1880 SDOI2009 Elaxia的路线 最短路+拓扑排序
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。