题解 P2149 【[SDOI2009]Elaxia的路线】

· · 题解

首先我们可以证明一个结论，两对点最短路的最长公共路径一定是一条连续的链：

因为两个点最短路上的每两个点之间的路径都是它们两个点的最短路，如果二号最短路与一号最短路在某个点交叉，又在某个点分开，那么两条路就不可能在别的点再交叉了，不然的话还不如在一号最短路继续走来的近。

OK,我的代码很宏（rong）伟（chang），算法是这样的，先对第一对点进行spfa，然后从终点开始把所有最短路经过的边都标记一下，标记的方法是这样的：如果当前点u离起点的距离是disu,对于u连出去的一条边，如果边的权值为w，而这条边对应的那个点v的disv=disu-w,那么从v到u的这条路径是形成最短路的合法路径，于是我们用类似BFS的操作，把这些边都标记了。

然后再对第二对点的起点终点各自做一次spfa，像对于第一对点一样，把它们存在于最短路中的合法的边标记一下，然后如果有边被重复标记，就加入一个新的图，最后dp求出最长的链就可以了。

这是我第一次做这种最短路找路径的题，没有看过任何一篇题解，于是YY出了这个神（shi）一样的方法，后来看到题解里面四遍spfa的方法感觉比我的好写多了，但实际上进行的都是差不多的操作，只是我找最短路合法路径的方法非常优（ma）雅（fan），而且我的时间复杂度也很优（dan）秀（teng），但是别开生面的方法才能锻炼自己的脑洞，希望大家多多加油。

下附优雅的代码

#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
using namespace std;
const int maxn=1500+10;
int x1,x2,y1,y2;
int a[maxn][maxn];
int n,m;
int dis[maxn],b[maxn][maxn];
int dp[maxn];
bool vis[maxn];
int e,nex[maxn*maxn],beg[maxn],to[maxn*maxn],w[maxn*maxn];
int E,Nex[maxn*maxn],Beg[maxn],To[maxn*maxn],W[maxn*maxn];
inline void add(int u,int v,int ww)
{
    to[++e]=v;
    nex[e]=beg[u];
    beg[u]=e;
    w[e]=ww;
}
inline void Add(int u,int v,int ww)
{
    To[++E]=v;
    Nex[E]=Beg[u];
    Beg[u]=E;
    W[E]=ww;
}
inline void spfa(int sta)
{
    queue<int>q;
    q.push(sta);
    memset(vis,0,sizeof(vis));
    memset(dis,127,sizeof(dis));
    dis[sta]=0;
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        vis[u]=0;
        for(register int i=beg[u];i;i=nex[i])
        {
            int v=to[i];
            if(dis[v]>dis[u]+w[i])
            {
                dis[v]=dis[u]+a[u][v];
                if(!vis[v])
                {
                    vis[v]=1;
                    q.push(v);
                }
            }
        }
    }
}
void create()
{
    queue<int>q;
    q.push(y1);
    memset(vis,0,sizeof(vis));
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        for(register int i=beg[u];i;i=nex[i])
        {
            int v=to[i];
        if(dis[u]-w[i]==dis[v])
        {
            b[u][v]=-1;
            if(!vis[v])
            {
                vis[v]=1;
                q.push(v);
            }
        }
        }
    }
}
void mark(int sta)
{
    queue<int>q;
    q.push(sta);
    memset(vis,0,sizeof(vis));
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        for(register int i=beg[u];i;i=nex[i])
        {
            int v=to[i];
        if(dis[u]-w[i]==dis[v])
        {
            if(b[u][v]==-1)
            {
                b[u][v]=a[u][v];
                Add(u,v,b[u][v]);
            }
            if(!vis[v])
            {
                vis[v]=1;
                q.push(v);
            }
        }
        }
    }
}
void dfs(int u)
{
    for(register int i=Beg[u];i;i=Nex[i])
    {
        int v=To[i];
        if(dp[v])
        {
            if(b[u][v]>0)dp[u]=max(dp[u],dp[v]+W[i]);
        }
        else
        {
            dfs(v);
            if(b[u][v]>0)dp[u]=max(dp[u],dp[v]+W[i]);
        }
    }
}
int main()
{
    scanf("%d%d",&n,&m);
    scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
    for(register int i=1;i<=m;++i)
    {
        int u,v,ww;
        scanf("%d%d%d",&u,&v,&ww);
        add(u,v,ww);
        add(v,u,ww);
        a[u][v]=a[v][u]=ww;
    }
    spfa(x1);
    create();
    spfa(x2);   
    mark(y2);
    spfa(y2);
    mark(x2);
    for(register int i=1;i<=n;++i)
        if(!dp[i])
            dfs(i);
    int ans=0;
    for(register int i=1;i<=n;++i)
        ans=max(ans,dp[i]);
    printf("%d\n",ans);

    return 0;
}