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，输入数据保证没有重边和自环。
直接上4遍SPFA，然后找到同为两条最短路上的边，进行拓扑排序，找到最大值。做完之后记得将某条路径的起点和终点交换再做一次
/*program from Wolfycz*/
#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define inf 0x7f7f7f7f
using namespace std;
typedef long long ll;
typedef unsigned int ui;
typedef unsigned long long ull;
inline int read(){
int x=0,f=1;char ch=getchar();
for (;ch<'0'||ch>'9';ch=getchar()) if (ch=='-') f=-1;
for (;ch>='0'&&ch<='9';ch=getchar()) x=(x<<1)+(x<<3)+ch-'0';
return x*f;
}
inline void print(int x){
if (x>=10) print(x/10);
putchar(x%10+'0');
}
const int N=1.5e3,M=5e5;
struct S1{
int pre[(M<<1)+10],now[N+10],child[(M<<1)+10],val[(M<<1)+10],tot;
S1(){tot=0;memset(now,0,sizeof(now));}
void init(){tot=0,memset(now,0,sizeof(now));}
void join(int x,int y,int z){pre[++tot]=now[x],now[x]=tot,child[tot]=y,val[tot]=z;}
void insert(int x,int y,int z){join(x,y,z),join(y,x,z);}
}Old,New;
struct S2{
int dis[N+10];
S2(){memset(dis,63,sizeof(dis));}
}Frw_1,Frw_2,Bck_1,Bck_2;
int h[N+10],F[N+10],deg[N+10];
int Ans,Dis_1,Dis_2,n,m;
bool vis[N+10];
void SPFA(int x,int *dis){
int head=0,tail=1;
h[1]=x,dis[x]=0,vis[x]=1;
while (head!=tail){
if (++head>N) head=1;
int Now=h[head];
for (int p=Old.now[Now],son=Old.child[p];p;p=Old.pre[p],son=Old.child[p]){
if (dis[son]>dis[Now]+Old.val[p]){
dis[son]=dis[Now]+Old.val[p];
if (!vis[son]){
if (++tail>N) tail=1;
vis[h[tail]=son]=1;
}
}
}
vis[Now]=0;
}
}
bool check_1(int x,int y,int v){return Frw_1.dis[x]+v+Bck_1.dis[y]==Dis_1;}
bool check_2(int x,int y,int v){return Frw_2.dis[x]+v+Bck_2.dis[y]==Dis_2;}
void Get_Ans(int S_1,int T_1,int S_2,int T_2){
New.init();
memset(F,0,sizeof(F));
memset(deg,0,sizeof(deg));
for (int x=1;x<=n;x++)
for (int p=Old.now[x],son=Old.child[p];p;p=Old.pre[p],son=Old.child[p])
if (check_1(x,son,Old.val[p])&&check_2(x,son,Old.val[p]))
New.join(x,son,Old.val[p]),deg[son]++;
int head=1,tail=0;
for (int i=1;i<=n;i++) if (!deg[i]) h[++tail]=i;
for (;head<=tail;head++){
int Now=h[head];
for (int p=New.now[Now],son=New.child[p];p;p=New.pre[p],son=New.child[p]){
F[son]=max(F[son],F[Now]+New.val[p]);
if (!(--deg[son])) h[++tail]=son;
}
}
for (int i=1;i<=n;i++) Ans=max(Ans,F[i]);
}
int main(){
n=read(),m=read();
int S_1=read(),T_1=read(),S_2=read(),T_2=read();
for (int i=1;i<=m;i++){
int x=read(),y=read(),z=read();
Old.insert(x,y,z);
}
SPFA(S_1,Frw_1.dis);
SPFA(S_2,Frw_2.dis);
SPFA(T_1,Bck_1.dis);
SPFA(T_2,Bck_2.dis);
Dis_1=Frw_1.dis[T_1];
Dis_2=Frw_2.dis[T_2];
Get_Ans(S_1,T_1,S_2,T_2);
swap(Frw_1,Bck_1);
Get_Ans(T_1,S_1,S_2,T_2);
printf("%d
",Ans);
return 0;
}