题意明确求两个人的最短路最长公共路径
1.所求是一段链,若答案不是连续路径,则两人会有再次相遇的情况,若有再次相遇则对另一方就不是最短路;
2.我们要求最长公共路径,就对每一个点跑最短路,也就是跑4遍,再把两个人重合的地方构建一个新图
如何判断重合,对于x1的最短路 有 dis[1][1~n],同理有dis[2][1~n],dis[3][1~n],dis[4][1~n].
对于一条边 u 到 v 长 w ,重合的条件是 dis[1][u] + dis[2][v] + w = dis[1][y1];这是第一个人的边满足是最短路的条件
第二个人同理 dis[3][u] + dis[4][v] + w = dis[3][y2]。 同时满足这两个条件就是重合的最短路
3.注意方向,由于第二次构图考虑方向,要把两个人同时同向和同时反向分开算。
#include <bits/stdc++.h>
using namespace std;
#define INF 0x7fffffff
const int N = 1550;
int dis[5][N];
int head1[N],head2[N];
int len[N];
int cnt1,cnt2;
int n,m;
struct Edge{
int w,v,nxt;
};
Edge edge1[N*N],edge2[N*N];
int in[N],book[N];
void add1(int u,int v,int w){
cnt1++;
edge1[cnt1].v = v;
edge1[cnt1].w = w;
edge1[cnt1].nxt = head1[u];
head1[u] = cnt1;
}
void add2(int u,int v,int w){
cnt2++;
edge2[cnt2].v = v;
edge2[cnt2].w = w;
edge2[cnt2].nxt = head2[u];
head2[u] = cnt2;
in[v]++;
}
void spfa(int id,int s){
memset(book,0,sizeof(book));
queue<int> q;while(!q.empty())q.pop();
for(int i=1;i<=n;i++)
dis[id][i] = INF;
dis[id][s]=0; book[s]=1; q.push(s);
while(!q.empty()){
int u=q.front(); book[u]=0; q.pop();
for(int w,v,i=head1[u];i;i=edge1[i].nxt){
v = edge1[i].v; w = edge1[i].w+dis[id][u];
if(dis[id][v]>w){
dis[id][v]=w;
if(!book[v]) book[v]=1,q.push(v);
}
}
}
}
void topo(){
queue<int> q;while(!q.empty())q.pop();
for(int i=1;i<=n;i++)if(!in[i])q.push(i);
while(!q.empty()){
int u = q.front(); q.pop();
for(int v,w,i=head2[u];i;i=edge2[i].nxt){
v = edge2[i].v; w = edge2[i].w + len[u];
len[v] = max(len[v],w);
in[v]--;
if(!in[v])q.push(v);
}
}
}
int main()
{
scanf("%d %d",&n,&m);
int x1,y1,x2,y2;
scanf("%d %d %d %d",&x1,&y1,&x2,&y2);
for(int i=1;i<=m;i++){
int u,v,w;
scanf("%d %d %d",&u,&v,&w);
add1(u,v,w);
add1(v,u,w);
}
spfa(1,x1); spfa(2,y1);
spfa(3,x2);
spfa(4,y2);
// printf("%d",dis[3][4]);
// printf("%d\n",dis[3][8]);
for(int i=1;i<=n;i++)
{
for(int j=head1[i];j;j=edge1[j].nxt)
{ int v = edge1[j].v,w = edge1[j].w;
if(dis[1][i]+dis[2][v]+w==dis[1][y1]){
if(dis[3][i]+dis[4][v]+w==dis[3][y2])
add2(i,v,w);
}
}
}
topo();
int ans = 0;
for(int i=1;i<=n;i++)ans=max(ans,len[i]);
//printf("%d\n",ans);
memset(len,0,sizeof(len));
memset(in,0,sizeof(in));
for(int i=1;i<=n;i++)
{
for(int j=head1[i];j;j=edge1[j].nxt)
{ int v = edge1[j].v,w = edge1[j].w;
if(dis[1][i]+dis[2][v]+w==dis[1][y1]){
if(dis[3][v]+dis[4][i]+w==dis[3][y2])
add2(i,v,w);
}
}
}
topo();
for(int i=1;i<=n;i++)ans=max(ans,len[i]);
printf("%d\n",ans);
return 0;
}