题解 P2109 【在一起】

檀黎斗·神 · 2017-10-08 19:15:55 · 题解

先以给出的四个点为起点的SPFA遍历一遍

以Elaxia的最短路和Elaxia、w的公共最短路建立一个新图

怎么判断某边是否为最短路呢？

其实可以通过判断dis(u,i)+len(i,j)+dis(j,v) == /！= dis(u,v)

接下来用拓扑排序递推：f[b[i].v]=max(f[b[i].v],f[temp]+b[i].w*b[i].f)

#include<queue>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
struct node{
    int u,v,w,nxt,f;
}a[4000005],b[4000005];
queue<int>q;
int n,m,cnt,ct2;
int h[2005],p[5],d[5][2005],h2[2005],r[2005],f[2005];
void add(int u,int v,int w)
{
    a[++cnt].u=u;
    a[cnt].v=v;
    a[cnt].w=w;
    a[cnt].nxt=h[u]; 
    h[u]=cnt;
}
void SPFA(int x)
{    
    bool v[1505]={0};
    for(int i=1;i<=n;++i) 
    if(i!=p[x]) d[x][i]=0x3f3f3f3f;
    q.push(p[x]);
    v[p[x]]=1;
    while( !q.empty() )
    {
        int now=q.front();
        q.pop(),v[now]=0;
        for(int i=h[now];i;i=a[i].nxt)
        {
            int to=a[i].v;
            if(d[x][to]>d[x][now]+a[i].w)
            {
                d[x][to]=d[x][now]+a[i].w;
                if(!v[to]) v[to]=1,q.push(to);
            } 
        }            
    }
}
int main()
{
    int x,y,z;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=4;++i) scanf("%d",&p[i]);
    for(int i=1;i<=m;++i)
    {
        scanf("%d%d%d",&x,&y,&z);
        add(x,y,z),add(y,x,z);
    }
    for(int i=1;i<=4;++i) SPFA(i);

    for(int i=1;i<=cnt;++i) //以Elaxia为主重建图 
     if(d[1][a[i].u]+a[i].w+d[2][a[i].v]==d[1][p[2]])
     {
         b[++ct2].u==a[i].u; 
         b[ct2].v=a[i].v; 
         b[ct2].w=a[i].w; 
         b[ct2].nxt=h2[a[i].u]; 
         h2[a[i].u]=ct2;
         if(d[3][a[i].u]+a[i].w+d[4][a[i].v]==d[3][p[4]]||d[4][a[i].u]+a[i].w+d[3][a[i].v]==d[3][p[4]]) b[ct2].f=1;
         r[a[i].v]++;
     }

    q.push(p[1]);
    int now;
    while(!q.empty())//拓扑排序找关键路径 
    {
        now=q.front(); q.pop();
        for(int i=h2[now];i;i=b[i].nxt)
        {
            --r[b[i].v];
            if(!r[b[i].v])
            {
                q.push(b[i].v);
                f[b[i].v]=max(f[b[i].v],f[now]+b[i].w*b[i].f);
            }
        }
    }
    printf("%d",f[p[2]]);
    return 0;
}