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

· · 题解

人生中A的第二道省选/NOI-……

这题好像是用某F姓大佬裸的增广路算法做的最长公共最短路模板。

其实理解算法并不难，先把以四个点为起点的SPFA跑一遍，然后建新图，只保留Elaxia的最短路（边权为0）和Elaxia、w的公共最短路。这里怎么判断某边是否是最短路呢？答案是用这个：

dis(s,i)+len(i,j)+dis(j,t)=dis(s,t)

下一步可以用拓扑排序递推：

f[b[i].t]=max(f[b[i].t],f[temp]+b[i].v*b[i].ok)

最后输出Elaxia终点的f值。

#include<iostream>
#include<cstdio>
#include<queue>
using namespace std;
queue <int> q;
struct node
{
    int f,t,nt,v,ok;
}a[2000005],b[2000005];
int n,m,head[1505],len,lt,s[6],ht[1505],visited[1505],dis[5][1505],f[1505],to[1505];
void spfa(int p)
{
    visited[s[p]]=1;
    q.push(s[p]);
    for (int i=1;i<=n;i++)
    if (i!=s[p])dis[p][i]=0x7fffffff/3;
    int temp;
    while (!q.empty())
    {
        temp=q.front();
        q.pop();
        visited[temp]=0;
        for (int i=head[temp];i;i=a[i].nt)
        {
            if (dis[p][a[i].t]>dis[p][temp]+a[i].v)
            {
                dis[p][a[i].t]=dis[p][temp]+a[i].v;
                if (visited[a[i].t]==0)visited[a[i].t]=1,q.push(a[i].t);
            }
        }
    }
}
int main()
{
    scanf("%d %d",&n,&m);
    for (int i=1;i<=4;i++)
    scanf("%d",&s[i]);
    int u,v,w;
    for (int i=1;i<=m;i++)//输入，双向建图
    {
        scanf("%d %d %d",&u,&v,&w);
        a[++len].t=v;
        a[len].f=u;
        a[len].v=w;
        a[len].nt=head[u];
        head[u]=len;
        a[++len].t=u;
        a[len].f=v;
        a[len].v=w;
        a[len].nt=head[v];
        head[v]=len;
    }
    for (int i=1;i<=4;i++)//四次SPFA
    spfa(i);
    for (int i=1;i<=len;i++)
    if (dis[1][a[i].f]+a[i].v+dis[2][a[i].t]==dis[1][s[2]])//重建图，以Elaxia为主
    {
        b[++lt].t=a[i].t;
        if (dis[3][a[i].f]+a[i].v+dis[4][a[i].t]==dis[3][s[4]]||dis[4][a[i].f]+a[i].v+dis[3][a[i].t]==dis[3][s[4]])
        b[lt].ok=1;
        b[lt].f=a[i].f;
        b[lt].v=a[i].v;
        b[lt].nt=ht[a[i].f];
        ht[a[i].f]=lt;
        to[a[i].t]++;
    }
    q.push(s[1]);//拓扑排序
    int temp;
    while (!q.empty())
    {
        temp=q.front();
        q.pop();
        for (int i=ht[temp];i;i=b[i].nt)
        {
            --to[b[i].t];
            if (to[b[i].t]==0)
            {
                q.push(b[i].t);
                f[b[i].t]=max(f[b[i].t],f[temp]+b[i].v*b[i].ok);
            }
        }
    }
    printf("%d",f[s[2]]);
}