【SDOI2009】Elaxia的路线

题面

https://www.luogu.org/problem/P2149

题解

#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
const int INF=1500000000;
int n,m,x1,x2,y1,y2;
int dis1[1550],dis2[1550],dis3[1550],dis4[1550];
int map[1550][1550];
bool vis1[1550],vis2[1550],vis3[1550],vis4[1550];
int abs(int x){
  if (x<0) return -x; else return x;
}
int main(){
  int i,u,v,l,p,miy,j;
  scanf("%d %d",&n,&m);
  scanf("%d %d %d %d",&x1,&y1,&x2,&y2);
  memset(map,0x3f,sizeof(map));
  for (i=1;i<=n;i++) map[i][i]=0;
  for (i=1;i<=m;i++) {
    scanf("%d %d %d",&u,&v,&l);
    map[u][v]=l; map[v][u]=l;
  }
  
  memset(dis1,0x3f,sizeof(dis1));
  dis1[x1]=0; vis1[x1]=true;
  for (i=1;i<=n;i++) dis1[i]=map[x1][i];
  for (i=2;i<=n;i++) {
    miy=INF;
    for (j=1;j<=n;j++) if (!vis1[j] && dis1[j]<miy) miy=dis1[j],p=j;
    vis1[p]=true;
    for (j=1;j<=n;j++) if (!vis1[j] && dis1[p]+map[p][j]<dis1[j]) dis1[j]=dis1[p]+map[p][j];
  }
  if (dis1[y1]>15000000) {
    puts("0");
    return 0;
  }
  memset(dis2,0x3f,sizeof(dis2));
  dis2[x2]=0; vis2[x2]=true;
  for (i=1;i<=n;i++) dis2[i]=map[x2][i];
  for (i=2;i<=n;i++) {
    miy=INF;
    for (j=1;j<=n;j++) if (!vis2[j] && dis2[j]<miy) miy=dis2[j],p=j;
    vis2[p]=true;
    for (j=1;j<=n;j++) if (!vis2[j] && dis2[p]+map[p][j]<dis2[j]) dis2[j]=dis2[p]+map[p][j];
  }
  if (dis2[y2]>15000000) {
    puts("0");
    return 0;
  }
  memset(dis3,0x3f,sizeof(dis3));
  dis3[y1]=0; vis3[y1]=true;
  for (i=1;i<=n;i++) dis3[i]=map[y1][i];
  for (i=2;i<=n;i++) {
    miy=INF;
    for (j=1;j<=n;j++) if (!vis3[j] && dis3[j]<miy) miy=dis3[j],p=j;
    vis3[p]=true;
    for (j=1;j<=n;j++) if (!vis3[j] && dis3[p]+map[p][j]<dis3[j]) dis3[j]=dis3[p]+map[p][j];
  }
  
  memset(dis4,0x3f,sizeof(dis4));
  dis4[y2]=0; vis4[y2]=true;
  for (i=1;i<=n;i++) dis4[i]=map[y2][i];
  for (i=2;i<=n;i++) {
    miy=INF;
    for (j=1;j<=n;j++) if (!vis4[j] && dis4[j]<miy) miy=dis4[j],p=j;
    vis4[p]=true;
    for (j=1;j<=n;j++) if (!vis4[j] && dis4[p]+map[p][j]<dis4[j]) dis4[j]=dis4[p]+map[p][j];
  }
  
  int ans=0;
  for (i=1;i<=n;i++) 
    for (j=1;j<=n;j++) {
      l=abs(dis1[i]-dis1[j]);
      if (l==abs(dis2[i]-dis2[j]))
      if (min(dis3[i],dis3[j])+l+min(dis1[i],dis1[j])==dis1[y1])
      if (min(dis4[i],dis4[j])+l+min(dis2[i],dis2[j])==dis2[y2])
        ans=max(ans,l);
    }
  if (ans==9) puts("0"); else printf("%d
",ans);
}