【JZOJ 4597】现世斩

Description

异变又发生了，魂魄妖梦作为幻想乡的一名自(cheng)机(guan)，主动前去解决异变。
我们用一个n个点、m条边的无向联通图来表示妖梦可选择的路线，妖梦从白玉楼出发，白玉楼被视为编号为1的点，编号为2——n的点是幻想乡的村庄，其中编号为n的村庄发生了异变。
每条边上可能会有一些妖怪袭击人类（然而妖梦是半人半灵），所以对于第i条边，妖梦需要t[i]分钟通过这条路。妖梦带了她的人符[现世斩]，可以使所有连接点x的边的通过时间变成1（x可以任意指定）。然而为了保留足够的力量解决异变，妖梦只会用这个符卡一次。妖梦想知道，她到达村庄n的最短时间是多少。

Solution

跟【GDOI 2016 Day2】SigemaGO 有点像，
先用DIJ预处理出所有点到S和T的距离，
枚举一个点q作为用符卡的点，答案就是： min(S,u)+min(v,T)(u,v∈q) $\min(S,u)+\min(v,T) (u,v \in q)$，
复杂度： O(nlog(n)+m) $O(n\log(n)+m)$

Code

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define efo(i,q) for(int i=A[q];i;i=B[i][0])
#define swapfa(q,w) swap(f[q],f[w]),swap(zx[fz[q]],zx[fz[w]]),swap(fz[q],fz[w])
#define TOP() (fz[1])
using namespace std;
typedef long long LL;
const int N=500500;
int read(int &n)
{char ch=' ';int q=0,w=1;for(;(ch!='-')&&((ch<'0')||(ch>'9'));ch=getchar());if(ch=='-')w=-1,ch=getchar();for(;ch>='0' && ch<='9';ch=getchar())q=q*10+ch-48;n=q*w;return n;
}
int n,m;
int B[2*N][3],A[N],B0=1;
LL f[N*2],INF,F[2][N],ans;
int zx[N],fz[2*N];
bool z[N];
void link(int q,int w,int e)
{B[++B0][0]=A[q],A[q]=B0,B[B0][1]=w,B[B0][2]=e;B[++B0][0]=A[w],A[w]=B0,B[B0][1]=q,B[B0][2]=e;
}
void down(int q)
{q=zx[q];while(f[q*2]<f[q]||f[q*2+1]<f[q]){if(f[q*2]>f[q*2+1])swapfa(q,q*2+1),q=q*2+1;else swapfa(q,q*2),q*=2;}
}
void up(int q)
{q=zx[q];while(f[q/2]>f[q]&&q!=1)swapfa(q,q/2),q/=2;
}
void DELT(int q){f[zx[q]]=INF,down(q);}
void dij(int E)
{int q,w,e,i;while(1){q=TOP();F[E][q]=f[zx[q]];if(z[q])break;z[q]=1;efo(i,q)if(!z[B[i][1]]&&f[zx[B[i][1]]]>f[zx[q]]+B[i][2]){f[zx[B[i][1]]]=f[zx[q]]+B[i][2];up(B[i][1]);}DELT(q);}
}
int main()
{freopen("cut.in","r",stdin);freopen("cut.out","w",stdout);int q,w,e;read(n),read(m);fo(i,1,m)read(q),read(w),read(e),link(q,w,e);memset(F,100,sizeof(F));memset(f,100,sizeof(f));INF=f[0];memset(z,0,sizeof(z));f[1]=0;fo(i,1,n)zx[i]=fz[i]=i;dij(0);memset(f,100,sizeof(f));INF=f[0];memset(z,0,sizeof(z));f[1]=0;fo(i,1,n)zx[i]=fz[i]=n-i+1;dij(1);ans=INF;efo(i,1)if(B[i][1]==n)ans=1;fo(i,1,n){LL Q=INF,W=INF;efo(j,i)Q=min(Q,F[0][B[j][1]]),W=min(W,F[1][B[j][1]]);if(Q!=INF&&W!=INF)ans=min(ans,2+Q+W);}printf("%lld\n",ans);return 0;
}