Description

最近，Elaxia和w的关系特别好，他们很想整天在一起，但是大学的学习太紧张了，他们 必须合理地安排两个人在一起的时间。Elaxia和w每天都要奔波于宿舍和实验室之间，他们 希望在节约时间的前提下，一起走的时间尽可能的长。 现在已知的是Elaxia和w所在的宿舍和实验室的编号以及学校的地图：地图上有N个路 口，M条路，经过每条路都需要一定的时间。 具体地说，就是要求无向图中，两对点间最短路的最长公共路径。

solution

题目比较坑，但可以AC.

首先这两个人并不都是从宿舍到实验室，所以要分情况讨论.

然后很容易想到取出两者公共最短路上的边，然后找最长路，注意这里有一点技巧

首先新图中存在环，不能用一般方法，我们就把边弄成单向边，就十分简单了，直接拓扑排序或记忆化搜索就可以弄出答案了.

具体方法就是我们强制规定边的方向，如从 \(x1->y1\) 最后做两边即可

#include <algorithm>

#include <iostream>

#include <cstdlib>

#include <cstring>

#include <cstdio>

#include <vector>

#include <queue>

#include <cmath>

#define RG register

#define il inline

#define iter iterator

#define Max(a,b) ((a)>(b)?(a):(b))

#define Min(a,b) ((a)<(b)?(a):(b))

using namespace std;

const int N=1505;

int head[N],nxt[N*N],to[N*N],num=1,n,m,dis[N*N],S1,S2,T1,T2;

void link(int x,int y,int z){

   nxt[++num]=head[x];to[num]=y;head[x]=num;dis[num]=z;}

int f[5][N],mod=N*10,q[N*10];bool vis[N],mark[N];

void spfa(int STA,int t){

   memset(f[t],127/3,sizeof(f[t]));

   memset(vis,0,sizeof(vis));

   int x,u,tail=0,sum=1;q[1]=STA;vis[STA]=1;f[t][STA]=0;

   while(tail!=sum){

      tail++;if(tail==mod)tail=0;x=q[tail];

      for(int i=head[x];i;i=nxt[i]){

         u=to[i];

         if(f[t][x]+dis[i]<f[t][u]){

            f[t][u]=f[t][x]+dis[i];

            if(!vis[u]){

               vis[u]=true;

               sum++;if(sum==mod)sum-=mod;q[sum]=u;

            }

         }

      }

      vis[x]=false;

   }

}

vector<int>G[2][N];int du[2][N],g[N],ans=0,D[N][N];bool inst[N];

queue<int>que;

void solve(bool t){

   int x,u;

   memset(g,0,sizeof(g));while(!que.empty())que.pop();

   for(int i=1;i<=n;i++)if(!du[t][i] && inst[i])que.push(i),g[i]=0;

   while(!que.empty()){

      x=que.front();que.pop();ans=Max(ans,g[x]);

      for(int i=0,Sz=G[t][x].size();i<Sz;i++){

         u=G[t][x][i];du[t][u]--;if(!du[t][u])que.push(u);

         g[u]=Max(g[u],g[x]+D[x][u]);

      }

   }

}

void work()

{

   int x,y,z;

   scanf("%d%d",&n,&m);

   scanf("%d%d%d%d",&S1,&T1,&S2,&T2);

   for(int i=1;i<=m;i++){

      scanf("%d%d%d",&x,&y,&z);

      link(x,y,z);link(y,x,z);

   }

   spfa(S1,1);spfa(T1,2);spfa(S2,3);spfa(T2,4);

   int fr,ti;

   for(int i=2;i<=num;i++){

      fr=to[i];ti=to[i^1];

      if(f[1][fr]+f[2][ti]+dis[i]!=f[1][T1])continue;

      if(f[3][fr]+f[4][ti]+dis[i]!=f[3][T2])continue;

      G[0][fr].push_back(ti);du[0][ti]++;inst[fr]=inst[ti]=true;

      D[fr][ti]=D[ti][fr]=dis[i];

   }

   solve(0);

   memset(inst,0,sizeof(inst));

   for(int i=2;i<=num;i++){

      fr=to[i];ti=to[i^1];

      if(f[1][ti]+f[2][fr]+dis[i]!=f[1][T1])continue;

      if(f[3][fr]+f[4][ti]+dis[i]!=f[3][T2])continue;

      G[1][ti].push_back(fr);du[1][fr]++;inst[fr]=inst[ti]=true;

      D[fr][ti]=D[ti][fr]=dis[i];

   }

   solve(1);

   printf("%d\n",ans);

}

int main()

{

	work();

	return 0;

}