题目描述
最近，Elaxia和w的关系特别好，他们很想整天在一起，但是大学的学习太紧张了，他们 必须合理地安排两个人在一起的时间。Elaxia和w每天都要奔波于宿舍和实验室之间，他们 希望在节约时间的前提下，一起走的时间尽可能的长。 现在已知的是Elaxia和w**所在的宿舍和实验室的编号以及学校的地图：地图上有N个路 口，M条路，经过每条路都需要一定的时间。 具体地说，就是要求无向图中，两对点间最短路的最长公共路径。
输入输出格式
输入格式：
第一行：两个整数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。
输出格式：
一行，一个整数，表示每天两人在一起的时间（即最长公共路径的长度）
输入输出样例
输入样例#1：
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：
3
说明
对于30%的数据，N ≤ 100；
对于60%的数据，N ≤ 1000；
对于100%的数据，N ≤ 1500，输入数据保证没有重边和自环。
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
SPFA+拓扑~
先以四个点为起始点SPFA四遍，然后把路径上同时在两最短路径上的边加成新树，再算出最长链长度就可以了~
算最长链用了拓扑，好像比一般用的两遍dfs好写？
加路径一定要按边加！按点加的话整个代码都要重构！不然会WA！
（要注意的是函数里面那个dis不能用memset，只能循环初始化……）
#include<cstdio>
#include<cstring>
#include<iostream>
#include<queue>
using namespace std;int n,m,x1,x2,y1,y2,x,y,val,fi[1501],cnt,fa[1501];
int disx1[1501],disx2[1501],disy1[1501],disy2[1501],dis1,dis2,cnt2;
int fi2[1501],ne2[1000001],w2[1000001],v2[1000001],du[1501],disss[1501],ans;
bool b[1501];
queue<int> q;struct node{int x,y,v,ne;
}a[1000001];void add(int u,int vv,int val)
{a[++cnt].y=vv;a[cnt].x=u;a[cnt].ne=fi[u];a[cnt].v=val;fi[u]=cnt;
}void spfa(int u,int dis[])
{for(int i=1;i<=n;i++) dis[i]=0x7f7f7f7f;b[u]=1;q.push(u);dis[u]=0;while(!q.empty()){int k=q.front();q.pop();b[k]=0;for(int i=fi[k];i;i=a[i].ne)if(dis[a[i].y]>dis[k]+a[i].v){dis[a[i].y]=dis[k]+a[i].v;if(!b[a[i].y]){b[a[i].y]=1;q.push(a[i].y);}}}
}int main()
{scanf("%d%d%d%d%d%d",&n,&m,&x1,&y1,&x2,&y2);for(int i=1;i<=m;i++){scanf("%d%d%d",&x,&y,&val);add(x,y,val);add(y,x,val);}spfa(x1,disx1);spfa(x2,disx2);spfa(y1,disy1);spfa(y2,disy2);dis1=disx1[y1];dis2=disx2[y2];for(int i=1;i<=cnt;i+=2){int k1=min(disx1[a[i].x],disx1[a[i].y])+min(disy1[a[i].x],disy1[a[i].y])+a[i].v,k2=min(disx2[a[i].x],disx2[a[i].y])+min(disy2[a[i].x],disy2[a[i].y])+a[i].v;if(k1==dis1 && k2==dis2){x=disx1[a[i].x]<disx1[a[i].y] ? a[i].x:a[i].y;y=disx1[a[i].x]<disx1[a[i].y] ? a[i].y:a[i].x;w2[++cnt2]=y;du[y]=1;ne2[cnt2]=fi2[x];fi2[x]=cnt2;v2[cnt2]=a[i].v;}}for(int i=1;i<=n;i++)if(!du[i]) q.push(i);while(!q.empty()){int k=q.front();q.pop();for(int i=fi2[k];i;i=ne2[i]){disss[w2[i]]=max(disss[w2[i]],disss[k]+v2[i]);ans=max(ans,disss[w2[i]]);du[w2[i]]--;if(!du[w2[i]]) q.push(w2[i]);}}printf("%d\n",ans);return 0;
}