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
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，输入数据保证没有重边和自环。
Source
Solution
补个条件：$m\leq 500000$
如果$dis_{s->u_i}+w_i=dis_{t->v_i}$，那么边$i$才可能成为答案
这些边组成的图一定是一个拓扑图，走一遍最长链即可。
其实主要的坑点在于因为是无向图，所以需要反着做一遍
也就是说，$x_1$->$y_1$和$y_2$->$x_2$的公共路径也可能是答案，也就是说，原题意是错的= =b
#include <bits/stdc++.h>
using namespace std;
struct edge
{
int v, w, nxt;
}e[];
int fst[][], dis[][], q[], indeg[];
int n, etot, sss1, ttt1, sss2, ttt2;
bool inq[]; void addedge(int *f, int u, int v, int w)
{
e[++etot] = (edge){v, w, f[u]}, f[u] = etot;
} bool check(int u, int i)
{
if(dis[][u] + e[i].w + dis[][e[i].v] != dis[][ttt1]) return false;
return dis[][u] + e[i].w + dis[][e[i].v] == dis[][ttt2];
} void SPFA(int sss, int *d)
{
int front = , back;
memset(d, , );
q[back = ] = sss, d[sss] = , inq[sss] = true;
while(front != back)
{
int u = q[++front & ];
front &= , inq[u] = false;
for(int i = fst[][u]; i; i = e[i].nxt)
if(d[e[i].v] > d[u] + e[i].w)
{
d[e[i].v] = d[u] + e[i].w;
if(!inq[e[i].v])
{
q[++back & ] = e[i].v;
back &= , inq[e[i].v] = true;
}
}
}
} int Topo_sort()
{
int front = , back = , ans = ;
for(int i = ; i <= n; ++i)
if(!indeg[i]) q[++back] = i;
while(front != back)
{
int u = q[++front];
for(int i = fst[][u]; i; i = e[i].nxt)
{
int v = e[i].v, w = e[i].w;
dis[][v] = max(dis[][v], dis[][u] + w);
if(!--indeg[e[i].v]) q[++back] = v;
}
}
for(int i = ; i <= n; ++i)
ans = max(ans, dis[][i]);
return ans;
} int main()
{
int m, u, v, w, ans;
scanf("%d%d", &n, &m);
scanf("%d%d%d%d", &sss1, &ttt1, &sss2, &ttt2);
for(int i = ; i <= m; ++i)
{
scanf("%d%d%d", &u, &v, &w);
addedge(fst[], u, v, w);
addedge(fst[], v, u, w);
}
SPFA(sss1, dis[]), SPFA(ttt1, dis[]);
SPFA(sss2, dis[]), SPFA(ttt2, dis[]);
for(int i = ; i <= n; ++i)
for(int j = fst[][i]; j; j = e[j].nxt)
if(check(i, j))
{
addedge(fst[], i, e[j].v, e[j].w);
++indeg[e[j].v];
}
ans = Topo_sort();
memset(fst[], , sizeof(fst[]));
memset(dis[], , sizeof(dis[]));
memset(indeg, , sizeof(indeg));
swap(sss2, ttt2);
SPFA(sss2, dis[]), SPFA(ttt2, dis[]);
for(int i = ; i <= n; ++i)
for(int j = fst[][i]; j; j = e[j].nxt)
if(check(i, j))
{
addedge(fst[], i, e[j].v, e[j].w);
++indeg[e[j].v];
}
ans = max(ans, Topo_sort());
printf("%d\n", ans);
return ;
}