Description
最近，Elaxia和w**的关系特别好，他们很想整天在一起，但是大学的学习太紧张了，他们 必须合理地安排两个人在一起的时间。Elaxia和w**每天都要奔波于宿舍和实验室之间，他们 希望在节约时间的前提下，一起走的时间尽可能的长。 现在已知的是Elaxia和w**所在的宿舍和实验室的编号以及学校的地图：地图上有N个路 口，M条路，经过每条路都需要一定的时间。 具体地说，就是要求无向图中，两对点间最短路的最长公共路径。
Input
第一行：两个整数N和M（含义如题目描述）。 第二行：四个整数x1、y1、x2、y2（1 ≤ x1 ≤ N，1 ≤ y1 ≤ N，1 ≤ x2 ≤ N，1 ≤ ≤ N），分别表示Elaxia的宿舍和实验室及w**的宿舍和实验室的标号（两对点分别 x1,y1和x2,y2）。 接下来M行：每行三个整数，u、v、l（1 ≤ u ≤ N，1 ≤ v ≤ N，1 ≤ l ≤ 10000），表 u和v之间有一条路，经过这条路所需要的时间为l。 出出出格格格式式式：：： 一行，一个整数，表示每天两人在一起的时间（即最长公共路径的长度）。
Output
一行，一个整数，表示每天两人在一起的时间（即最长公共路径的长度）
Sample Input
9 10
1 6 7 8
1 2 1
2 5 2
2 3 3
3 4 2
3 9 5
4 5 3
4 6 4
4 7 2
5 8 1
7 9 1
Sample Output
3
HINT
对于30%的数据，N ≤ 100；
对于60%的数据，N ≤ 1000；
对于100%的数据，N ≤ 1500，输入数据保证没有重边和自环。

题解

这题其实挺简单的吧。。
你就把最短路径图建出来
然后暴力枚举每一个点，说是在这个点相遇
然后暴力跑一下，这里要记忆化一下，然后可以视为O(n)的
然后这里倒着走的话答案也是算的。。
于是你要把x2,y2交换一下再跑一次（TYB大佬说的，我也没这个WA过）
然后我一开始由于记忆化写炸了，就GG了QAQ

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

#include<cstdio>
#include<queue>
#include<cstring>
#include<algorithm>
#include<iostream>
using namespace std;
const int N=1502;
const int M=N*N;
int n,m;
int x1,y1,x2,y2;
struct qq
{int x,y,z,last;
}s[M];int num,last[N];
void init (int x,int y,int z)
{num++;s[num].x=x;s[num].y=y;s[num].z=z;s[num].last=last[x];last[x]=num;
}
int f[N];
queue<int> q;
bool in[N];
void SPFA (int xx)//以这个为起点 
{memset(in,false,sizeof(in));memset(f,127,sizeof(f));q.push(xx);f[xx]=0;in[xx]=true;while (!q.empty()){int x=q.front();q.pop();for (int u=last[x];u!=-1;u=s[u].last){int y=s[u].y;if (f[y]>f[x]+s[u].z){f[y]=f[x]+s[u].z;if (in[y]==false){in[y]=true;q.push(y);}}}in[x]=false;}
}
qq s1[M/2];int num1,last1[N];
void init1 (int x,int y,int z)
{num1++;s1[num1].x=x;s1[num1].y=y;s1[num1].z=z;s1[num1].last=last1[x];last1[x]=num1;
}
int ok[N];//这个点能不能成功到达终点 -1:不知道 0:不能 1:能
bool a[N],b[N];//这个点能不能到 
void dfs (int x)
{   if (ok[x]!=-1) return ;ok[x]=0;for (int u=last1[x];u!=-1;u=s1[u].last){int y=s1[u].y;dfs(y);if (ok[y]==1) {
   /*printf("%d\n",x);*/ok[x]=1;return ;}}
}
void prepare ()
{SPFA(x1);num1=0;memset(last1,-1,sizeof(last1));for (int u=1;u<=num;u++)if (f[s[u].x]+s[u].z==f[s[u].y])//这条边可以用init1(s[u].x,s[u].y,s[u].z); memset(ok,-1,sizeof(ok));ok[y1]=1;for (int u=1;u<=n;u++) {dfs(u);if (ok[u]==1) a[u]=true;else a[u]=false;}SPFA(x2);num1=0;memset(last1,-1,sizeof(last1));for (int u=1;u<=num;u++)if (f[s[u].x]+s[u].z==f[s[u].y])init1(s[u].x,s[u].y,s[u].z);memset(ok,-1,sizeof(ok));ok[y2]=1;for (int u=1;u<=n;u++) {dfs(u);if (ok[u]==1) b[u]=true;else b[u]=false;}
}
int vis[N];//如果在这个点都一样的话最优代价是多少 
void dfs1 (int x)
{if (vis[x]!=-1) return ;vis[x]=0;for (int u=last1[x];u!=-1;u=s1[u].last){int y=s1[u].y;if (a[y]==true&&b[y]==true){dfs1(y);vis[x]=max(vis[x],vis[y]+s1[u].z);}}
}   
int ans=0;
void solve ()
{memset(vis,-1,sizeof(vis));for (int u=1;u<=n;u++){if (a[u]==true&&b[u]==true)//这个可以作为起点了dfs1(u);//在这个地方相遇 ans=max(vis[u],ans);}
}
int main()
{num=0;memset(last,-1,sizeof(last));scanf("%d%d",&n,&m);scanf("%d%d%d%d",&x1,&y1,&x2,&y2);for (int u=1;u<=m;u++){int x,y,z;scanf("%d%d%d",&x,&y,&z);init(x,y,z);init(y,x,z);}prepare();solve();swap(x2,y2);prepare();solve();printf("%d\n",ans);return 0;
}