P2149 [SDOI2009]Elaxia的路线 题解
讲道理，这是一道质量比较高的图论综合题，牵涉到了许多图论知识点，还加上dp，是一道很好的题目。
分析题目：其实就是求无向图中，两对点间最短路的最长公共路径。
讲讲具体思路：先跑4遍SPFA，每个人的起点和重点各作为起点跑一次，然后再重新构图，再在新图上跑一遍拓扑，顺便还要dp出答案
SPFA相信都会，就不说了。
说说重新构图。其实也还好理解，就是在原来那个图里，把不是最短路的边都弄掉，只剩下在最短路上的。怎么判断一条边是不是最短路上的？如果到这条边的起点的值加这条边的权值加这条边的终点之后的值就是最短路的值，那么这条路就可能在最短路上，就是了，如果也同时在另一条最短路上，就打上ok记号
然后是dp环节
dp[x]表示到点x的时候最长公共路径。
怎么dp呢？我们考虑在拓扑排序中dp，如果一个点x没有出边了才去管他，他的值就是连他的那个点的dp值，如果是两个最短路的公共路径，就还要加上这条路的权值，否则就不用
最后dp[终点]就是答案了
#include <bits/stdc++.h>
using namespace std;
inline int read(){
int x=0,f=1;char ch=getchar();
while(ch>'9'||ch<'0'){if(ch=='-')f=-f;ch=getchar();}
while(ch<='9'&&ch>='0'){x=x*10+ch-'0';ch=getchar();}return x*f;
}
struct node{
int next,to,w,x,ok;
}e[2000005],b[2000005];
int n,m,xx,xxx,yy,yyy,cnt,vis[1510],head[1510],dis[5][1505],headd[1510],cntt,to[1510],dp[1510];
void spfa(int u,int p){
vis[u]=1;
queue<int>q;
q.push(u);
for(int i=1;i<=n;i++){
if(i!=u)dis[p][i]=0x7fffffff/3;
}
while(!q.empty()){
int l=q.front();
q.pop();
vis[l]=0;
for(int i=head[l];i;i=e[i].next){
int to=e[i].to;
if(dis[p][to]>dis[p][l]+e[i].w){
dis[p][to]=dis[p][l]+e[i].w;
if(!vis[to]){
vis[to]=1;q.push(to);
}
}
}
}
}
int main(){
n=read();m=read();
xx=read();yy=read();
xxx=read();yyy=read();
for(int i=1;i<=m;i++){
int x=read(),y=read(),z=read();
cnt++;e[cnt].to=y;e[cnt].next=head[x];head[x]=cnt;e[cnt].w=z;e[cnt].x=x;
cnt++;e[cnt].to=x;e[cnt].next=head[y];head[y]=cnt;e[cnt].w=z;e[cnt].x=y;
}
spfa(xx,1);spfa(yy,2);spfa(xxx,3);spfa(yyy,4);
for(int i=1;i<=cnt;i++){
if(dis[1][e[i].x]+e[i].w+dis[2][e[i].to]==dis[1][yy]){
cntt++;
b[cntt].to=e[i].to;
if(dis[3][e[i].x]+e[i].w+dis[4][e[i].to]==dis[3][yyy]||dis[4][e[i].x]+e[i].w+dis[3][e[i].to]==dis[3][yyy])b[cntt].ok=1;
b[cntt].x=e[i].x;
b[cntt].w=e[i].w;
b[cntt].next=headd[e[i].x];
headd[e[i].x]=cntt;
to[e[i].to]++;
}
}
queue<int>q;
q.push(xx);
while(!q.empty()){
int l=q.front();
q.pop();
for(int i=headd[l];i;i=b[i].next){
to[b[i].to]--;
if(to[b[i].to]==0){
q.push(b[i].to);
dp[b[i].to]=max(dp[b[i].to],dp[l]+b[i].w*b[i].ok);
}
}
}
cout<<dp[yy];
return 0;
}