题解 P2149 【[SDOI2009]Elaxia的路线】
昨天wa了很长在这个题目上 所以特地写篇题解来说清楚这道题的坑点！
注意仔细看题目：求两个人走的最短路径的公共最长的部分。
我第一个反应是直接求出最短路径然后取两个人相同的部分即可。然后wa的很惨因为题目说的意思让取两个人各自的唯一一条最短路径的公共最长部分。
显然最短路不止一条，且两个人的最短路是相交或相向的都是可以累积答案的，这就非常的烦。。
统计答案的方式（这是我在写这道题最迷的地方根本不知道如何得到答案）：
-
注意会跑最短路也要会求最短路径。
-
对于答案的统计最好的莫过于分类讨论 路径是同向还是相向
-
经过一下午+一晚上的分析这道题统计答案最好的还是重新建图然后topsort跑答案是最简洁的。
对于1求得话我既然是dij跑的最短路自然dij求路径这里注意bfs也可以求需要spfa类似的迭代思想。
对于2我们求出1的最短路径后在求二的最短路径的时候就可以判断是同向还是相向了，此时直接建图即可。
对于3这里不要迷建的图是关于最短路径 至于最短路径一定是一个DAG所以可以topsort的。相信你看了上面统计答案的方式一定会明白的！（觉得好点个赞顶上去
code:
//#include<bits/stdc++.h>
#include<iomanip>
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<queue>
#include<deque>
#include<cmath>
#include<ctime>
#include<cstdlib>
#include<stack>
#include<algorithm>
#include<vector>
#include<cctype>
#include<utility>
#include<set>
#include<bitset>
#include<map>
#define INF 2147483646
#define ll long long
#define min(x,y) (x>y?y:x)
#define max(x,y) (x>y?x:y)
#define R register
#define up(p,i,n) for(int i=p;i<=n;++i)
using namespace std;
char buf[1<<15],*fs,*ft;
inline char getc()
{
return (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<15,stdin),fs==ft))?0:*fs++;
}
inline int read()
{
int x=0,f=1;char ch=getc();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getc();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getc();}
return x*f;
}
inline void put(int x)
{
x<0?x=-x,putchar('-'):0;
int num=0;char ch[50];
while(x)ch[++num]=x%10+'0',x/=10;
num==0?putchar('0'):0;
while(num)putchar(ch[num--]);
putchar('\n');return;
}
const int MAXN=1510;
int n,m,len,h,t,ans,len1;
int s1,s2,s3,s4,maxx,st;
int s[MAXN],f[MAXN],ru[MAXN];
int vis[MAXN],dis[MAXN],b[2][MAXN][MAXN];
int lin[MAXN],nex[MAXN*MAXN<<1],ver[MAXN*MAXN<<1],e[MAXN*MAXN<<1];
int lin1[MAXN],nex1[MAXN*MAXN<<1],ver1[MAXN*MAXN<<1],e1[MAXN*MAXN<<1];
priority_queue<pair<int,int> > q;
inline void add(int x,int y,int z)
{
ver[++len]=y;
nex[len]=lin[x];
lin[x]=len;
e[len]=z;
}
inline void add1(int x,int y,int z)
{
ver1[++len1]=y;
nex1[len1]=lin1[x];
lin1[x]=len1;
e1[len1]=z;
}
inline void dij(int x,int y,int p)
{
memset(vis,0,sizeof(vis));
memset(dis,10,sizeof(dis));
q.push(make_pair(0,x));dis[x]=0;
while(q.size())
{
int te=q.top().second;
q.pop();
if(vis[te])continue;
vis[te]=1;
for(int i=lin[te];i;i=nex[i])
{
int tn=ver[i];
if(dis[tn]>dis[te]+e[i])
{
dis[tn]=dis[te]+e[i];
q.push(make_pair(-dis[tn],tn));
}
}
}
memset(vis,0,sizeof(vis));
q.push(make_pair(dis[y],y));vis[y]=1;
while(q.size())
{
int te=q.top().second;
q.pop();
for(int i=lin[te];i;i=nex[i])
{
int tn=ver[i];
if(dis[tn]==dis[te]-e[i])
{
b[p][tn][te]=1;
if(b[p^1][tn][te])++ru[te],add1(tn,te,e[i]);
if(!vis[tn])
{
q.push(make_pair(dis[tn],tn));
vis[tn]=1;
}
}
}
}
}
inline void topsort()
{
h=t=0;for(int i=1;i<=n;++i)if(!ru[i])s[++t]=i;
while(h++<t)
{
int te=s[h];
for(int i=lin1[te];i;i=nex1[i])
{
int tn=ver1[i];
f[tn]=max(f[tn],f[te]+e1[i]);
--ru[tn];
if(!ru[tn])s[++t]=tn,ans=max(ans,f[tn]);
}
}
}
int main()
{
//freopen("1.in","r",stdin);
n=read();m=read();
s1=read();s2=read();s3=read();s4=read();
for(int i=1;i<=m;++i)
{
int x,y,z;
x=read();y=read();z=read();
add(x,y,z);add(y,x,z);
}
dij(s1,s2,0);
dij(s3,s4,1);
topsort();
memset(vis,0,sizeof(vis));
q.push(make_pair(dis[s4],s4));vis[s4]=1;
while(q.size())
{
int te=q.top().second;
q.pop();
for(int i=lin[te];i;i=nex[i])
{
int tn=ver[i];
if(dis[tn]==dis[te]-e[i])
{
if(b[0][te][tn])++ru[te],add1(tn,te,e[i]);
if(!vis[tn])
{
q.push(make_pair(dis[tn],tn));
vis[tn]=1;
}
}
}
}
topsort();
put(ans);
return 0;
}