四次SPFA求最短路
枚举边 使得他是两个人的公共路径
i->to
dist[start][i]+len+dist[end][to]==dist[1][end]
反向也有可能 再次枚举即可 建新图
跑拓扑排序 更新ans最大值
#include <bits/stdc++.h>
using namespace std;
#define MOD (int)(1e9+7)
#define ll long long
#define db(a) (cout<<"->"<<a<<endl)
#define FORP(i,a,b) for(int i=a;i<=b;++i)
#define pb push_back
#define mp(a,b) make_pair(a,b)
typedef pair<int,int> Pair;
#define maxn 302000
int pt[10];
vector<Pair> G[maxn],E[maxn];
void add(int u,int v,int w){G[u].pb(mp(v,w));G[v].pb(mp(u,w));
}
int dist[10][20000];
int inq[20000];
void init(){memset(inq,0,sizeof(inq));
}
void spfa(int index){init();memset(dist[index],0x3f,sizeof(dist[index]));queue<int> q;int x=pt[index];dist[index][x]=0;q.push(x);inq[x]=1;while(!q.empty()){int u=q.front();q.pop();for(int i=0;i<G[u].size();++i){int to=G[u][i].first;int cost=G[u][i].second;if(dist[index][u]+cost<dist[index][to]){dist[index][to]=cost+dist[index][u];if(!inq[to]){inq[to]=1;q.push(to);}}}inq[u]=0;}
}
int in[maxn],d[maxn];
int n,m;
int ans=0;
void topologysort(){memset(d,0,sizeof(d));queue<int> q;FORP(i,1,n) if(!in[i]) q.push(i);while(!q.empty()){int u=q.front();q.pop();ans=max(ans,d[u]);for(int i=0;i<E[u].size();++i){int to=E[u][i].first;int cost=E[u][i].second;d[to]=max(d[to],d[u]+cost);if(--in[to]==0) q.push(to);}}
}
int main(){cin>>n>>m;cin>>pt[1]>>pt[2]>>pt[3]>>pt[4];FORP(i,1,m){int u,v,w;cin>>u>>v>>w;add(u,v,w);}FORP(i,1,4) spfa(i);//两个人同一个方向FORP(i,1,n){
//枚举所有的边FORP(j,0,(int)G[i].size()-1){int to=G[i][j].first;int len=G[i][j].second;if(len+dist[1][i]+dist[2][to]==dist[1][pt[2]]&&dist[3][i]+len+dist[4][to]==dist[3][pt[4]]){E[i].pb(mp(to,len));in[to]++;}}}topologysort();//两个人反向memset(in,0,sizeof(in));FORP(i,1,n) E[i].clear();FORP(i,1,n){
//枚举所有的边FORP(j,0,(int)G[i].size()-1){int to=G[i][j].first;int len=G[i][j].second;if(len+dist[1][i]+dist[2][to]==dist[1][pt[2]]&&dist[3][to]+len+dist[4][i]==dist[3][pt[4]]){E[i].pb(mp(to,len));in[to]++;}}}topologysort();cout<<ans<<endl;return 0;
}