洛谷2149（最长公共路径)

· · 题解

这道题是一道图论+dp题，也是我目前做到的第二道图论+dp题QWQ。但是我一开始没有想到要外跑dp，所以两次尝试案例答案都错误。然后我就看了@我不是纸张啊这位大佬的博客emmmm....

以下是我的代码的:

inline void dijkstra(int start){
    ++ans;
    priority_queue<pair<int,int> >q;
    memset(vis,0,sizeof(vis));
    fp(i,1,n) dis[i][ans]=0x3f3f3f3f;dis[start][ans]=0;
    dis[start][ans]=0;q.push(make_pair(0,start));
    while(!q.empty()){
        int temp=q.top().second;q.pop();
        if(vis[temp]) continue;
        vis[temp]=1;
        for(int i=head[temp];i;i=edge[i].prev){
            int to=edge[i].to;
            if(dis[to][ans]>dis[temp][ans]+edge[i].w){
                 dis[to][ans]=dis[temp][ans]+edge[i].w;
             q.push(make_pair(-dis[to][ans],to));
            }
        }
    }
}

这个是dij板子，就不用多说了。

inline void csh(){
    dijkstra(x1);dijkstra(y11);dijkstra(x2);dijkstra(y22);
}

两个人的起点和终点分别跑一次最短路，即总共四次。

接下来就是如何处理满足条件的边集合了： 1：首先符合条件的边肯定是属于最短路径中的。所以我们可以遍历每一条边 即这条边的权值+正向dis+反向dis即是整条路径的长度，若其值等于最短路径的值，即把它加入到新图中。

2：同时每条边要去判断是不是属于另一个人的最短路径，若是，代码中就将此边标记为1.

下面就贴我的ac代码了

#include<bits/stdc++.h>
using namespace std;
inline int read(){
    char c=getchar();int x=0,f=1;
    while(c<'0'||c>'9'){if(c=='-') f=-1;c=getchar();}
    while(c>='0'&&c<='9') x=x*10+c-'0',c=getchar();
    return x*f;
}
inline void out(int a){
    if(a<0)
    {
        putchar('-');
        a=-a;
    }
    if(a>9) out(a/10);
    putchar(a%10+'0');
}
int n,m,x1,y11,x2,y22;
struct Edge{
    int from,to,prev,flag,w;
}edge[1000000],e[1000000];
int cnt,head[2000];
inline void add(int x,int y,int w){
    edge[++cnt].to=y;
    edge[cnt].from=x;
    edge[cnt].w=w;
    edge[cnt].prev=head[x];
    head[x]=cnt;
}
int he[2000],ans,h;
inline void adds(int x,int y,int w){
    e[++h].to=y;
    e[h].from=x;
    e[h].w=w;
    e[h].prev=he[x];
    he[x]=h;
}
#define fp(i,w,n) for(int i=w;i<=n;i++)
inline void start(){
    n=read(),m=read();
    x1=read(),y11=read(),x2=read(),y22=read();
    fp(i,1,m){
        int x,y,w;x=read(),y=read(),w=read();
        add(x,y,w);add(y,x,w);
    }
}
int vis[2000],dis[2000][5];
inline void dijkstra(int start){
    ++ans;
    priority_queue<pair<int,int> >q;
    memset(vis,0,sizeof(vis));
    fp(i,1,n) dis[i][ans]=0x3f3f3f3f;dis[start][ans]=0;
    dis[start][ans]=0;q.push(make_pair(0,start));
    while(!q.empty()){
        int temp=q.top().second;q.pop();
        if(vis[temp]) continue;
        vis[temp]=1;
        for(int i=head[temp];i;i=edge[i].prev){
           int to=edge[i].to;
           if(dis[to][ans]>dis[temp][ans]+edge[i].w){
               dis[to][ans]=dis[temp][ans]+edge[i].w;
               q.push(make_pair(-dis[to][ans],to));
           }
        }
    }
}
inline void csh(){
    dijkstra(x1);dijkstra(y11);dijkstra(x2);dijkstra(y22);
}
int arrive[2000],dp[2000];
inline void solve(){
    csh();
    fp(i,1,cnt){
        int from=edge[i].from,to=edge[i].to;
      if(dis[from][1]+edge[i].w+dis[to][2]==dis[y11][1]){
        adds(from,to,edge[i].w);
          if(dis[from][3]+edge[i].w+dis[to][4]==dis[y22][3]||dis[from][4]+edge[i].w+dis[to][3]==dis[y22][3]){
                e[h].flag=1;
            }
            arrive[to]++;
        }
    }
    queue<int> q;
    q.push(x1);
    while(!q.empty()){
        int temp=q.front();q.pop();
        for(int i=he[temp];i;i=e[i].prev){
        int to=e[i].to;arrive[to]--;
        dp[to]=max(dp[to],dp[temp]+e[i].w*e[i].flag);
        if(!arrive[to]) q.push(to);
        }
    }
    out(dp[y11]),putchar('\n');
}
int main(){
    start();
    solve();
    return 0;
}

以下是大佬@我不是纸张啊 的代码中我没看懂的部分

if(to[b[i].to]==0){
     q.push(b[i].to);
     dp[b[i].to]=max(dp[b[i].to],dp[l]+b[i].w*b[i].ok);
}

以下是大佬的解释:

怎么dp呢？我们考虑在拓扑排序中dp，如果一个点x没有出边了才去管他，他的值就是连他的那个点的dp值，如果是两个最短路的公共路径，就还要加上这条路的权值，否则就不用.

但是我认为这样会漏掉很多数组滚动的可能性，可能大佬的思想比较深厚吧。