P2149题解

· · 题解

1 思路

本题可以用 4 次最短路解决，不需要拓扑或动规。目前题解里应该没有重复的。

我们要建好图。我们要将一条无向边看成两条端点、耗时（即边权）相同，方向相反的有向边。

设第 i 条边的起点为 e[i].u，终点为 e[i].v，耗时为 e[i].w，走这条边能跟 Elaxia 在一起的时间为 e[i].c（初始为 0）。

接下来，跑 2 次最短路。一次从 Elaxia 的起点开始，一次从 Elaxia 的终点开始。此时，无向边与 2 条有向边没有差别。但以后会有的。

然后，对于第 i 条有向边，设 u=e[i].u，v=e[i].v。如果：

从起点到 u 的距离+u 与 v 的距离+终点到 v 的距离=从起点到终点的距离

那么将 e[i].c 设为 e[i].w。但不要对反向边这么标记。

很明显，如果两人均走最短路，那么公共路径（如果有的话）必定是一条链。而且，两人在公共路径上要么一直同向行走，要么一直反向行走（注意，反向行走也算“一起走”）。

但是，按照上面的标记法，反向行走不会被考虑。

那么，我们可以只将同向行走算“一起走”，但是反向行走不算。

然后再跑两次“最优路”，一次从 w** 的起点开始，一次从终点开始（也就是反着走）。

最优路，就是在最短路的基础上，与 Elaxia 一起走的时间长者优先。

最后，输出这两次“最优路”中，能跟 Elaxia 一起走的时间最长的。

2 代码与记录

#include<cstdio>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;
#define max_n 1500//最大点数
#define inf 0x2f2f2f2f//一个很大的数
int n;//点数
int m;//边数
int sx1,ex1;//Elaxia的起点与终点
int sx2,ex2;//w**的起点与终点
struct E{//边结构体
    int u,v,w,c,nx;//起点、终点、耗时、能否一起、下一条边
}e[max_n*max_n*2+20];//边
int ei=0;//边的下标
int fir[max_n+2];//最初的边
struct D{//距离结构体
    int w,c;//耗时，一起时间
}dis[4][max_n+2];
bool operator<(D a,D b){//比较哪个优
    if(a.w^b.w)return a.w<b.w;
    return a.c>b.c;
    //返回1说明a比b优，反之亦然
}
struct W{//路径结构体
    int u;
    D d;
    bool operator<(const W &a)const{
        return a.d<d;
    }
};
W f;//队首
priority_queue<W>q;//优先队列
void addedge(int u,int v,int w,int c){//连边
    e[++ei]=(E){u,v,w,c,fir[u]}; fir[u]=ei;
}
void work(const int fl,const int sx){//求最短路
    for(int i=1;i<=n;++i)dis[fl][i]=(D){inf,-inf};
    while(!q.empty())q.pop();
    dis[fl][sx]=(D){0,0};
    q.push((W){sx,dis[fl][sx]});
    while(!q.empty()){
        f=q.top();
        q.pop();
        if(dis[fl][f.u]<f.d)continue;
        for(int i=fir[f.u],v;i;i=e[i].nx){
            v=e[i].v;
            D d=(D){f.d.w+e[i].w,f.d.c+e[i].c};
            if(d<dis[fl][v]){
                dis[fl][v]=d;
                q.push((W){v,d});
            }
        }
    }
}
int main(){
    #ifndef ONLINE_JUDGE
    freopen("P2149_1.in","r",stdin);
    freopen("P2149_1.out","w",stdout);
    #endif
    scanf("%d%d%d%d%d%d",&n,&m,&sx1,&ex1,&sx2,&ex2);
    for(int i=1,u,v,w;i<=m;++i){
        scanf("%d%d%d",&u,&v,&w);
        addedge(u,v,w,0);
        addedge(v,u,w,0);
    }
    work(0,sx1);//从Elaxia起点到各点的最短路
    work(1,ex1);//从Elaxia终点到各点的最短路
    for(int u=1;u<=n;++u){
        for(int i=fir[u],v;i;i=e[i].nx){
            v=e[i].v;
            if(dis[0][u].w+e[i].w+dis[1][v].w==dis[0][ex1].w)e[i].c=e[i].w;
        }
    }
    work(2,sx2);//从w**起点到各点的最优路
    work(3,ex2);//从w**终点到各点的最优路
    printf("%d\n",max(dis[2][ex2].c,dis[3][sx2].c));
    return 0;
}

记录传送门

By dengziyue