BZOJ3161 : 孤舟蓑笠翁

显然求出每个点到所有关键点的最短路和次短路即可，答案就是每个关键点的次短路。

设$f[i][j][0]$表示左手在$i$，右手在$j$的解，$f[i][j][1]$表示左手在$i$，右手在$j$，且左手已经动了右手还没开始动的解，然后BFS即可。

时间复杂度$O(n(n+m))$。

#include<cstdio>

const int N=1010,M=10010;

int n,m,K,dmi,dma,i,j,k,x,y,z,vip[N][N],ans[N*N],e[2][N],v[M],nxt[M],ed,h,t,q[N*N*4][5];

struct P{int x,y;P(){}P(int _x,int _y){x=_x,y=_y;}}a[N],f[N][N][2],g[N][N][2];

inline void read(int&a){char c;while(!(((c=getchar())>='0')&&(c<='9')));a=c-'0';while(((c=getchar())>='0')&&(c<='9'))(a*=10)+=c-'0';}

inline void add(int&x,int y){v[++ed]=y;nxt[ed]=x;x=ed;}

inline int abs(int x){return x>0?x:-x;}

inline bool check(int x,int y){

  int d=abs(a[x].x-a[y].x)+abs(a[x].y-a[y].y);

  return dmi<=d&&d<=dma;

}

inline void ext(int x,int y,int z,int a,int b){

  if(!z&&!check(x,y))return;

  if(g[x][y][z].y)return;

  if(f[x][y][z].y==b)return;

  q[++t][0]=x,q[t][1]=y,q[t][2]=z,q[t][3]=a,q[t][4]=b;

  if(!f[x][y][z].y)f[x][y][z]=P(a,b);else g[x][y][z]=P(a,b);

}

int main(){

  read(n),read(m),read(dmi),read(dma);

  for(i=1;i<=n;i++)read(a[i].x),read(a[i].y);

  read(K);

  for(i=1;i<=K;i++)read(x),read(y),vip[x][y]=i;

  while(m--){

    read(x),read(y),read(z);

    add(e[z][x],y),add(e[z][y],x);

  }

  for(i=1;i<=n;i++)add(e[0][i],i),add(e[1][i],i);

  for(h=i=1;i<=n;i++)for(j=1;j<=n;j++)if(vip[i][j])ext(i,j,0,0,vip[i][j]);

  while(h<=t){

    x=q[h][0],y=q[h][1],z=q[h][2],j=q[h][3]+1-z,k=q[h++][4];

    for(i=e[z][z?y:x];i;i=nxt[i])ext(z?x:v[i],z?v[i]:y,z^1,j,k);

  }

  for(i=1;i<=n;i++)for(j=1;j<=n;j++)if(vip[i][j])ans[vip[i][j]]=g[i][j][0].y?g[i][j][0].x:-1;

  for(i=1;i<=K;i++)printf("%d\n",ans[i]);

  return 0;

}