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

· · 题解

** 发现神题一道

方法楼下已经说的很清楚。。但是我一开始对于代码实现还是有点不明白

比如dis(x1,i)+dis(i,j)+dis(j,y1)中的dis(j,y1)怎么算？

= =因为一开始只想到SPFA两次（x1,x2各一次）

后来发现需要四次，从x1,x2,y1,y2各一次

开四个数组dx1,dx2,dy1,dy2记录距离

这样判断就好多了，还有一些代码细节的地方不懂的童鞋可以借鉴一下[delete]别问我抄代码怎么破[/delete]

后面找公共边我是把所有边枚举了一遍

然后重新构一张图跑dp求最长路径


#include<queue>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn=1500+10;
const int maxm=maxn*maxn*2;
const int INF=(1<<30);
struct Edge{
    int u,v,d;
    Edge(){}
    Edge(int u,int v,int d):u(u),v(v),d(d){}
}e[maxm];

int n,m,x1,x2,y1,y2;

int u[maxm],v[maxm],ecnt=0;
int first[maxn],next[maxm];

void add_edge(int u,int v,int d)
{
    next[ecnt]=first[u];first[u]=ecnt;e[ecnt++]=Edge(u,v,d);
    next[ecnt]=first[v];first[v]=ecnt;e[ecnt++]=Edge(v,u,d);
}

void init_data()
{
    cin>>n>>m;
    cin>>x1>>y1>>x2>>y2;
    for(int i=1;i<=n;i++) first[i]=-1;
    for(int i=1,uu,vv,d;i<=m;i++)
    {
        scanf("%d%d%d",&uu,&vv,&d);
        add_edge(uu,vv,d);
    }
}

int inq[maxn];
void SPFA(int s,int d[])
{
    queue<int>q;
    for(int i=1;i<=n;i++) inq[i]=0,d[i]=INF;
    d[s]=0;inq[s]=1;
    q.push(s);

    while(!q.empty())
    {
        int x=q.front();q.pop();
        inq[x]=false;
        for(int i=first[x];i!=-1;i=next[i])
        {
            Edge &edge=e[i];
            if(d[x]<INF&&d[edge.v]>d[x]+edge.d)
            {
                d[edge.v]=d[x]+edge.d;
                if(!inq[edge.v])
                {
                    q.push(edge.v);
                    inq[edge.v]=1;
                }
            }
        }
    }
}

int nnext[maxm],ffirst[maxm],eecnt=0,in[maxn];
Edge ee[maxm];
void aadd_edge(int u,int v,int d)
{
    nnext[eecnt]=ffirst[u];ffirst[u]=eecnt;ee[eecnt++]=Edge(u,v,d);
    in[u]=in[v]=1;
}

int dx1[maxn];
int dy1[maxn];
int dx2[maxn];
int dy2[maxn];

void common()
{
    for(int i=1;i<=n;i++) ffirst[i]=-1;
    for(int i=0;i<ecnt;i++)
    {
        if(dx1[e[i].u]+e[i].d+dy1[e[i].v]==dx1[y1])
          if(dx2[e[i].u]+e[i].d+dy2[e[i].v]==dx2[y2]||dx2[e[i].v]+e[i].d+dy2[e[i].u]==dx2[y2])
          {
              if(dx1[e[i].u]>dx1[e[i].v]) aadd_edge(e[i].v,e[i].u,e[i].d);
              else  aadd_edge(e[i].u,e[i].v,e[i].d);
          }
    }
}

int dp[maxn];
int f(int x)
{
    if(dp[x]!=0) return dp[x];
    for(int i=ffirst[x];i!=-1;i=nnext[i])
    {
        dp[x]=max(dp[x],f(ee[i].v)+ee[i].d); 
    } 
    return dp[x];
}

int main()
{
    init_data();
    SPFA(x1,dx1);
    SPFA(y1,dy1);
    SPFA(x2,dx2);
    SPFA(y2,dy2);
    common();
    for(int i=1;i<=n;i++)
      if(in[i]&&!dp[i])
        f(i);
    int ans=0;
    for(int i=1;i<=n;i++)
      ans=max(ans,dp[i]);
    printf("%d",ans);
    return 0;
}

**