https://www.luogu.org/problem/show?pid=2149
题目描述
最近，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，输入数据保证没有重边和自环。
以给定的4个点跑4遍最短路，
确定每条同时在在于两点间最短路上的边，更新ans
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <queue> #define max(a,b) (a>b?a:b)
#define min(a,b) (a<b?a:b)
inline void read(int &x)
{
x=; register char ch=getchar();
for(; ch>''||ch<''; ) ch=getchar();
for(; ch>=''&&ch<=''; ch=getchar()) x=x*+ch-'';
}
const int INF(0x3f3f3f3f);
const int N(+);
const int M(2e6+);
int n,m,s1,s2,t1,t2;
int head[N],sumedge,hed[N],sum;
struct Edge {
int v,next,w;
Edge(int v=,int next=,int w=):v(v),next(next),w(w){}
}edge[M<<],e[M];
struct Road {
int u,v,w;
Road(int u=,int v=,int w=):u(u),v(v),w(w){}
}road[M];
inline void ins(int u,int v,int w)
{
edge[++sumedge]=Edge(v,head[u],w);
head[u]=sumedge;
edge[++sumedge]=Edge(u,head[v],w);
head[v]=sumedge;
} bool vis[N];
int dis[N][];
struct Node {
int pos,dis;
Node() { pos=; dis=; }
bool operator < (const Node &x)const
{
return dis>x.dis;
}
}u,v;
inline void Dijkstra(int s,int op)
{
memset(vis,,sizeof(vis));
std::priority_queue<Node>que;
for(int i=; i<=n; ++i) dis[i][op]=INF;
u.pos=s; u.dis=dis[s][op]=; que.push(u);
for(; !que.empty(); )
{
u=que.top(); que.pop();
if(vis[u.pos]) continue; vis[u.pos]=;
for(int i=head[u.pos]; i; i=edge[i].next)
{
v.pos=edge[i].v;
if(dis[v.pos][op]>dis[u.pos][op]+edge[i].w)
{
v.dis=dis[v.pos][op]=dis[u.pos][op]+edge[i].w;
que.push(v);
}
}
}
} int rd[N],val[N],ans;
inline void add(int u,int v,int w)
{
e[++sum]=Edge(v,hed[u],w);
hed[u]=sum; rd[v]++;
}
inline int Top_sort()
{
int ret=;
std::queue<int>que;
for(int i=; i<=n; ++i)
if(!rd[i]) que.push(i);
for(int u,v; !que.empty(); )
{
u=que.front(); que.pop();
for(int i=hed[u]; i; i=e[i].next)
{
v=e[i].v;
if(val[v]<val[u]+e[i].w)
val[v]=val[u]+e[i].w,ret=max(ret,val[v]);
if(--rd[v]==) que.push(v);
}
}
return ret;
} inline bool check(int x)
{
return (dis[x][]+dis[x][]==dis[t1][])&&(dis[x][]+dis[x][]==dis[t2][]);
} int Presist()
{
read(n),read(m),read(s1);
read(t1),read(s2),read(t2);
for(int u,v,w,i=; i<=m; ++i)
read(u),read(v),read(w),
ins(u,v,w),road[i]=Road(u,v,w);
Dijkstra(s1,); Dijkstra(s2,);
Dijkstra(t1,); Dijkstra(t2,);
for(int i=; i<=n; ++i) if(check(i))
for(int j=i+; j<=n; ++j) if(check(j))
ans=max(ans,std::abs(dis[i][]-dis[j][]));
printf("%d\n",ans);
return ;
} int Aptal=Presist();
int main(int argc,char*argv[]){;}