首页 > 代码库 > BZOJ 2725: [Violet 6]故乡的梦 最短路+线段树
BZOJ 2725: [Violet 6]故乡的梦 最短路+线段树
2725: [Violet 6]故乡的梦
Time Limit: 20 Sec Memory Limit: 128 MBSubmit: 678 Solved: 204
[Submit][Status][Discuss]
Description
Input
Output
Sample Input
6 7
1 2 1
2 3 1
3 4 2
4 5 1
5 6 1
1 3 3
4 6 3
1 6
4
1 2
1 3
4 3
6 5
1 2 1
2 3 1
3 4 2
4 5 1
5 6 1
1 3 3
4 6 3
1 6
4
1 2
1 3
4 3
6 5
Sample Output
7
6
Infinity
7
6
Infinity
7
HINT
Source
interviewstreet--Going office
想法:
先跑出一条最短路径(S,T),如果没删除上面的边就直接输出最短路。
如果枚举一条边(x,y),那么最短路一定能被(S-x)+(x,y)+(y,T)表示出来。所以如果要删(u,v),那就要枚举一条边(x,y),要求dis(x)<=dis(u)&&dis(y)>=dis(v),这样就保证(S,x),(y,T)不经过(u,v)了。于是按dis()顺序枚举(S,T)路径上的边,用线段树维护合法的最小值。
当然如果是有向图,就不能只用dis(x)<=dis(u)&&dis(y)>=dis(v)来限制不经过这条边了。
#include<cstdio> #include<algorithm> typedef long long ll; const int len(200000),lem(200000); const ll INF(0x7fffffffffffffff); struct Node{int nd,nx,co;}bot[lem*2+10];int tot=1,first[len+10]; int flag[len+10],last[len+10],tmp[len+10],Fr[len+10],To[len+10]; ll dis[len+10],Go[len+10],Bk[len+10],ans[len+10]; struct Data{int num;ll dis;}h[lem*2+10];int top; struct ABC{int a,b,pos;ll c;}Edge[lem*2+10]; int n,m,x,y,c,S,T,Q; ll min(ll a,ll b){return a>b?b:a;} bool cmp(Data A,Data B){return A.dis>B.dis;} bool cmp2(ABC A,ABC B){return Go[A.a]<Go[B.a];} void swap(int &a,int &b){if(a==b)return;a^=b;b^=a;a^=b;} void add(int a,int b,int c){bot[++tot]=(Node){b,first[a],c};first[a]=tot;} template <class T>void read(T &x) { x=0;int f=0;char c=getchar(); while((c<‘0‘||c>‘9‘)&&c!=‘-‘)c=getchar(); if(c==‘-‘)f=1,c=getchar(); while(c>=‘0‘&&c<=‘9‘){x=x*10+c-‘0‘;c=getchar();} x=f?-x:x; } struct MAP { ll axle[len*2+10]; int up; void ins(ll x){axle[++up]=x;} void deal() { std::sort(axle+1,axle+1+up); int _up=1;//偷懒专用变量命名 for(int i=2;i<=up;i++)if(axle[i]!=axle[i-1])axle[++_up]=axle[i]; up=_up; } int two(ll x) { int num=up; for(int mid,l=1,r=up;l<=r;)(axle[mid=(l+r)>>1]<=x)?num=mid,l=mid+1:r=mid-1; return num; } }Map; struct SMT { int nx[lem*2+10][2],K,stot; ll small[lem*2+10]; void build(int &k,int L,int R) { k=++stot; small[k]=INF; if(L==R)return; int MID=(L+R)>>1; build(nx[k][0],L,MID),build(nx[k][1],MID+1,R); } void change(int k,int L,int R,int x,ll y) { small[k]=min(small[k],y); if(L==R)return; int MID=(L+R)>>1; (x<=MID)?change(nx[k][0],L,MID,x,y):change(nx[k][1],MID+1,R,x,y); } ll query(int k,int L,int R,int x) { if(L==x)return small[k]; int MID=(L+R)>>1; return (x>MID)?query(nx[k][1],MID+1,R,x): min(small[nx[k][1]],query(nx[k][0],L,MID,x)); } }tree; int dfs(int x) { if(tmp[x])return tmp[x]; if(flag[x])return x; tmp[last[x]]=dfs(last[x]); return tmp[last[x]]; } void Dij(int s,int t,int ty) { for(int i=1;i<=n;i++)dis[i]=INF; dis[s]=0; h[top=1]=(Data){s,0}; Data now; while(top) { now=h[1],std::pop_heap(h+1,h+1+top,cmp),top--; while(dis[now.num]!=now.dis&&top)now=h[1],std::pop_heap(h+1,h+1+top,cmp),top--; if(dis[now.num]!=now.dis&&!top)break; for(int v=first[now.num];v;v=bot[v].nx) if(dis[bot[v].nd]>now.dis+bot[v].co) { dis[bot[v].nd]=now.dis+bot[v].co; last[bot[v].nd]=now.num; h[++top]=(Data){bot[v].nd,dis[bot[v].nd]}; std::push_heap(h+1,h+1+top,cmp); } } if(ty==0) for(int v=t;v;v=last[v])flag[v]=1; if(ty==1) for(int i=1;i<=n;i++) if(dis[i]!=INF)tmp[i]=dfs(i);//O(n) }//O(mlogm) void Get() { int x=S,Ei=2; while(x!=T) { if(!flag[x])break;flag[x]=0; for(int v=first[x];v;v=bot[v].nx) if(flag[bot[v].nd]&&Go[x]+bot[v].co==Go[bot[v].nd]) { while(Go[Edge[Ei].a]<=Go[x]&&Ei<=tot) { if((Edge[Ei].pos^1)!=v&&Edge[Ei].pos!=v&&(Edge[Ei].pos^1)!=Edge[Ei-1].pos) tree.change(tree.K,1,Map.up,Map.two(Go[Edge[Ei].b]),Edge[Ei].c); Ei++; } ans[bot[v].nd]=tree.query(tree.K,1,Map.up,Map.two(Go[bot[v].nd])); if(ans[bot[v].nd]==INF)ans[bot[v].nd]=-1; last[bot[v].nd]=x; x=bot[v].nd; break; } } }//O(m+nlogn) int main() { // freopen("C.in","r",stdin); // freopen("C.out","w",stdout); read(n);read(m); for(int i=1;i<=m;i++) { read(x),read(y),read(c); add(x,y,c),add(y,x,c); } read(S),read(T); Dij(S,T,0);flag[0]=1; if(dis[T]!=INF)Dij(S,T,1);for(int i=1;i<=n;i++)Fr[i]=tmp[i],Go[i]=dis[i],tmp[i]=0; if(dis[T]!=INF)Dij(T,S,1);for(int i=1;i<=n;i++)To[i]=tmp[i],Bk[i]=dis[i],tmp[i]=0; for(int i=1;i<=n;i++) for(int v=first[i];v;v=bot[v].nx) { Edge[v]=(ABC){i,bot[v].nd,v,0}; if(Go[Edge[v].a]>Go[Edge[v].b])swap(Edge[v].a,Edge[v].b); // if(Go[Edge[v].a]!=INF&&Bk[Edge[v].b]!=INF) Edge[v].c=Go[Edge[v].a]+Bk[Edge[v].b]+bot[v].co; Edge[v].a=Fr[i]; Edge[v].b=To[bot[v].nd]; if(Go[Edge[v].a]>Go[Edge[v].b])swap(Edge[v].a,Edge[v].b); // else Edge[v].c=INF; } std::sort(Edge+2,Edge+1+tot,cmp2); for(int i=1;i<=n;i++)Map.ins(Go[i]); Map.deal(); tree.build(tree.K,1,Map.up); for(int i=1;i<=n;i++)last[i]=0; Get(); if(Go[T]==INF)Go[T]=-1; read(Q); for(int i=1;i<=Q;i++) { read(x),read(y); if(last[x]==y)swap(x,y); ll sum=(last[y]==x)?ans[y]:Go[T]; if(sum==-1)printf("Infinity\n");else printf("%lld\n",sum); } return 0; }
BZOJ 2725: [Violet 6]故乡的梦 最短路+线段树
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。