题意简述：求两条给定起点终点最短路的最长公共路径。
首先最长公共路径一定是两条最短路的公共最长链的部分。至少一定在两条最短路上。
考虑如何求出一条路径是否包含于一条最短路，只要路径 \(x\rightarrow y\) 满足：
\[dis_{st\rightarrow x}+w_{x\rightarrow y}+dis_{y\rightarrow ed}=dis_{st\rightarrow ed}
\]
就说明该路径为最短路上的一条边。
但是重合部分并不一定是两条路径的重合部分，有可能是两条路径的多种情况混在一块，先来考虑简单情况，两条最短路相加，重合部分方向（记 \(st\) 走到 \(ed\) 为方向）要么是相同，要么是相反，这是好证的；同理，若两个重合部分方向相同且连在一起，则说明他们一定是在同一条最短路上的。所以我们分别保留方向相同，方向相反的边，依次做一遍 \(dag\) 上的 \(dp\) 即可。
点击查看代码
#include<bits/stdc++.h>
using namespace std;
#define PII pair<int,int>
const int N=1600;
int n,m;
int s1,e1,s2,e2;
struct node{
int to,w;
};
vector<node> g[N],g2[N];
int dis[10][N];
int f[N];
priority_queue<PII> q;
void dij(int st,int opt) {
memset(dis[opt],0x3f,sizeof(dis[opt]));
memset(f,0,sizeof(f));
while(q.size()) q.pop();
q.push({0,st}); dis[opt][st]=0;
while(q.size()) {
int x=q.top().second; q.pop();
if(f[x]) continue;
f[x]=1;
for(auto t:g[x]) {
int y=t.to,w=t.w;
if(dis[opt][y]>dis[opt][x]+w) {
dis[opt][y]=dis[opt][x]+w;
if(!f[y]) q.push({-dis[opt][y],y});
}
}
}
}
int deg[N],len[N];
void topo() {
queue<int> q;
while(q.size()) q.pop();
for(int i=1;i<=n;i++) if(!deg[i]) q.push(i);
while(q.size()) {
int x=q.front(); q.pop();
for(node t:g2[x]) {
int y=t.to,w=t.w;
deg[y]--;
len[y]=max(len[y],len[x]+w);
if(!deg[y]) q.push(y);
}
}
}
int main() {
cin>>n>>m;
cin>>s1>>e1>>s2>>e2;
for(int i=1;i<=m;i++) {
int x,y,z; cin>>x>>y>>z;
g[x].push_back({y,z});
g[y].push_back({x,z});
}
dij(s1,1); dij(e1,2); dij(s2,3); dij(e2,4);
for(int i=1;i<=n;i++) {
for(auto t:g[i]) {
int x=i,y=t.to,w=t.w;
if(dis[1][x]+w+dis[2][y]==dis[1][e1]&&dis[3][x]+w+dis[4][y]==dis[3][e2]) {
g2[x].push_back({y,w});
deg[y]++;
}
}
}
topo();
int ans=0;
for(int i=1;i<=n;i++) ans=max(ans,len[i]);
for(int i=1;i<=n;i++) {
g2[i].clear();
deg[i]=0; len[i]=0;
}
for(int i=1;i<=n;i++) {
for(auto t:g[i]) {
int x=i,y=t.to,w=t.w;
if(dis[1][x]+w+dis[2][y]==dis[1][e1]&&dis[3][y]+w+dis[4][x]==dis[3][e2]) {
g2[x].push_back({y,w});
deg[y]++;
}
}
}
topo();
for(int i=1;i<=n;i++) ans=max(ans,len[i]);
cout<<ans;
return 0;
}