比较综合的题，求最短路肯定都会，但是考虑如何计算最长的公共部分的长度。一开始我想的是跑最短路时记录路径，然后在路径上找公共部分。但是这样其实是错误的想法。因为他们的最短路线可能有多个交集。
实际上需要跑四遍最短路，分别是两人的起点和终点各跑一次，然后将最短路径上的点建新图，同时标记哪些点是公共部分。如果途中存在最短路，那么最短路构成的路径一定是有向无环图，一定没有环。而有向无环图我们又可以考虑拓扑排序从起点开始求最长的路径。所以说这道题就这样完了。
dp方程就是 dp[i]表示到第i个点的最长公共路径 dp[i]=max(dp[i],dp[j]+flag*w[i->j])。flag是标记，标记i->j之间的边是否在公共路径上。w则是边权。
代码如下：
#include<bits/stdc++.h> using namespace std; const int maxn=1e6+7; struct node{ int nxt,to,from,val; }edge[maxn*4]; struct node1{ int nxt,to,from,val,flag; }edge1[maxn*5]; int head1[maxn],num; int head[maxn],cnt; void add(int x,int y,int v){ edge[++cnt].nxt=head[x]; edge[cnt].from=x; edge[cnt].to=y; edge[cnt].val=v; head[x]=cnt; } int dis[6][maxn]; bool vis[maxn]; int deg[maxn]; int n,m,s1,t1,s2,t2; int x,y,v; void newadd(int x,int y,int v){ edge1[++num].nxt=head1[x]; edge1[num].from=x; edge1[num].to=y; edge1[num].val=v; head1[x]=num; } void dijkstra(int flag,int x){ priority_queue<pair<long long,int> >q; for(int i=1;i<=n;i++) dis[flag][i]=0x3f3f3f3f; memset(vis,false,sizeof(vis)); q.push(make_pair(0,x)); dis[flag][x]=0; while(!q.empty()){ int u=q.top().second; q.pop(); if(vis[u]) continue; vis[u]=true; for(int i=head[u];i;i=edge[i].nxt){ int v=edge[i].to; if(dis[flag][v]>dis[flag][u]+edge[i].val){ dis[flag][v]=dis[flag][u]+edge[i].val; q.push(make_pair(-dis[flag][v],v)); } } } } void work(){ for(int i=1;i<=cnt;i++){ int x=edge[i].from,y=edge[i].to; if(dis[1][x]+edge[i].val+dis[3][y]==dis[1][t1]){ newadd(x,y,edge[i].val); if(dis[2][x]+edge[i].val+dis[4][y]==dis[2][t2]||dis[2][y]+edge[i].val+dis[4][x]==dis[2][t2]) edge1[num].flag=1; deg[y]++; } } } queue<int> q; int dp[maxn]; int ans; void topo(){ q.push(s1); while(!q.empty()){ int u=q.front(); q.pop(); for(int i=head1[u];i;i=edge1[i].nxt){ int v=edge1[i].to; dp[v]=max(dp[v],dp[u]+edge1[i].val*edge1[i].flag); deg[v]--; if(!deg[v]) q.push(v); } } for(int i=1;i<=n;i++) ans=max(ans,dp[i]); printf("%d ",ans); } int main(){ scanf("%d%d",&n,&m); scanf("%d%d%d%d",&s1,&t1,&s2,&t2); for(int i=1;i<=m;i++){ scanf("%d%d%d",&x,&y,&v); add(x,y,v);add(y,x,v); } dijkstra(1,s1); dijkstra(2,s2); dijkstra(3,t1); dijkstra(4,t2); work(); topo(); return 0; }