题目描述
最近，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。 出出出格格格式式式：：： 一行，一个整数，表示每天两人在一起的时间（即最长公共路径的长度）。
输出格式
一行，一个整数，表示每天两人在一起的时间（即最长公共路径的长度）
分析题目可得：
最短路的公共部分肯定是两个人的最短路径图的交集。所以我们先给每个人求出最短路径图，并求出它们的交集。
接下来我们需要求交集上的最长路。我们知道有环的图是没有最长路的，但是最短路径图是有向无环图，那么交集同理。所以我们在交集上做拓扑动规求最长路即可。
但是题目中有一个细节：公共部分不代表必须同向行走。
所以我们正反都判一次。
时间复杂度为O((N+M)log(N+M))
#include<iostream>
#include<cstring>
#include<cstdio>
#include<queue>
#define maxn 1501
#define maxm 1000001
using namespace std;
struct graph{
struct edge{
int to,dis,next;
edge(){}
edge(const int &_to,const int &_dis,const int &_next){ to=_to,dis=_dis,next=_next; }
}e[maxm<<1];
int head[maxn],k;
inline void init(){ memset(head,-1,sizeof head); }
inline void add(const int &u,const int &v,const int &w){ e[k]=edge(v,w,head[u]),head[u]=k++; }
}a,b;
int dis[maxn][5],ind[maxn],len[maxn];
bool vis[maxn];
int n,m,s1,t1,s2,t2,ans;
inline int read(){
register int x(0),f(1); register char c(getchar());
while(c<'0'||'9'<c){ if(c=='-') f=-1; c=getchar(); }
while('0'<=c&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
return x*f;
}
inline void dijkstra(const int &s,const int &d){
priority_queue< pair<int,int>,vector< pair<int,int> >,greater< pair<int,int> > > q;
memset(vis,false,sizeof vis),dis[s][d]=0;
q.push(make_pair(0,s));
while(q.size()){
int u=q.top().second; q.pop();
if(vis[u]) continue; vis[u]=true;
for(register int i=a.head[u];~i;i=a.e[i].next){
int v=a.e[i].to;
if(dis[v][d]>dis[u][d]+a.e[i].dis) dis[v][d]=dis[u][d]+a.e[i].dis,q.push(make_pair(dis[v][d],v));
}
}
}
inline void rebuild(const int &op){
for(register int u=1;u<=n;u++){
for(register int j=a.head[u];~j;j=a.e[j].next){
int v=a.e[j].to;
if(op==1&&dis[u][1]+a.e[j].dis+dis[v][2]==dis[t1][1]&&dis[u][3]+a.e[j].dis+dis[v][4]==dis[t2][3]) b.add(u,v,a.e[j].dis),ind[v]++;
if(op==2&&dis[u][1]+a.e[j].dis+dis[v][2]==dis[t1][1]&&dis[u][4]+a.e[j].dis+dis[v][3]==dis[t2][3]) b.add(u,v,a.e[j].dis),ind[v]++;
}
}
}
inline void topo(){
queue<int> q;
for(register int i=1;i<=n;i++) if(!ind[i]) q.push(i);
while(q.size()){
int u=q.front(); q.pop();
for(register int i=b.head[u];~i;i=b.e[i].next){
int v=b.e[i].to;
len[v]=max(len[v],len[u]+b.e[i].dis),ind[v]--;
if(!ind[v]) q.push(v);
}
}
for(register int i=1;i<=n;i++) ans=max(ans,len[i]);
}
int main(){
a.init(),b.init();
n=read(),m=read(),s1=read(),t1=read(),s2=read(),t2=read();
for(register int i=1;i<=m;i++){
int u=read(),v=read(),w=read();
a.add(u,v,w),a.add(v,u,w);
}
memset(dis,0x3f,sizeof dis);
dijkstra(s1,1),dijkstra(t1,2),dijkstra(s2,3),dijkstra(t2,4);
rebuild(1),topo();
memset(ind,0,sizeof ind),memset(len,0,sizeof len),b.init();
rebuild(2),topo();
printf("%d
",ans);
return 0;
}