CF2000G Call During the Journey - 洛谷

~~（从未设想过的道路，蒟蒻独立 AC 了道蓝。）~~

题目大意

给定

n

个点和

m

条边，边权有限制，在接电话的时候不能快速通过。

对于在接电话的时候经过，有两种处理方法：

等限制过了再过。
慢一点过。

求最晚什么时候出发。

解题思路

Dijkstra

很明显经过花费的时间就是边权，编号

1

的十字路口是起点，编号

n

的十字路口是终点，也无负边权，考虑跑 Dijkstra。

跑一下最短路显然会寄，也就是你不知道在你跑最短路的时候会不会有时限，动态处理似乎也并不好做。

直接枚举出发时间显然复杂度会爆炸，看来我们还得结合另一种算法。

二分

~~（从未设想过的道路，有一天最短路竟然会成为二分的 check() 函数。）~~

晚出发的在时限内过了，早出发的肯定也能过，因此具有单调性，考虑二分出发时间。

分类讨论

同时，我们就可以知道在跑最短路的时候某时某刻有没有时限了，那么直接分类讨论。

已经打完电话了。
坐车的时候还没有打电话。
正好碰上打电话，考虑等着坐车，还是直接走，取最小值。

复杂度与优化

这样的话，复杂度是

O(\log{t_{0}}(m+n)\log{n})

，算下来大概是

5\times 10^{7}

，比较危险，因此考虑优化。

在最短路的优先队列里，如果已经大于 $t_{0}$ ，就可以结束最短路了，但是你也不确定 $dis_{n}$ 是否已经访问到了，所以直接 break;，而非 return false;。
不要开 long long，显然有了前面的优化，最大不过 $t_{0}+l_{2}$ ，都是最大 $10^{9}$ ，而 $2 \times 10^{9}$ 显然不会爆 int。
快读（AC 代码附赠快读板子）。

AC 代码

CPP

#include<iostream>
#include<cstring>
#include<cstdio>
#include<queue>
using namespace std;
inline int read(){
    char c=getchar();
    bool flag=false;
    while(!isdigit(c)){
        if(c=='-')flag=true;
        c=getchar();
    }
    int x=0;
    while(isdigit(c)){
        x=(x<<1)+(x<<3)+(c^48);
        c=getchar();
    }
    return flag?-x:x;
}
//快读
const int N=1e5+5,M=1e5+5;
int T,n,m,k,pre[N],t0,t1,t2,dis[N];
void init(){
    k=0;
    memset(pre,0,sizeof(pre));
}
//初始化图
struct edge{
    int v,l1,l2;
    int next;
}e[M<<1];
void add(int u,int v,int l1,int l2){
    e[++k]={v,l1,l2,pre[u]};
    pre[u]=k;
}
struct node{
    int v,w;
    bool operator<(const node&x)const{
        return x.w<w;
    }
};
priority_queue<node>p;
bool b[N];
bool dijkstra(int s,int t){
    memset(dis,0x3f,sizeof(dis));
    memset(b,false,sizeof(b));
    dis[s]=t;
    while(!p.empty())p.pop();
    p.push({s,t});
    while(!p.empty()){
        int u=p.top().v;
        p.pop();
        if(dis[u]>t0)break;
        if(b[u])continue;
        b[u]=true;
        for(int i=pre[u];i;i=e[i].next){
            if(dis[u]>=t2){
                if(dis[u]+e[i].l1<dis[e[i].v]){
                    dis[e[i].v]=dis[u]+e[i].l1;
                    p.push({e[i].v,dis[e[i].v]});
                }
            }
            else if(dis[u]+e[i].l1<=t1){
                if(dis[u]+e[i].l1<dis[e[i].v]){
                    dis[e[i].v]=dis[u]+e[i].l1;
                    p.push({e[i].v,dis[e[i].v]});
                }
            }
            else{
                int d=min(t2+e[i].l1,dis[u]+e[i].l2);
                if(d<dis[e[i].v]){
                    dis[e[i].v]=d;
                    p.push({e[i].v,dis[e[i].v]});
                }
            }
        }
    }
    return dis[n]<=t0;
}
//Dijkstra
int main(){
    T=read();
    while(T--){
        n=read();
        m=read();
        t0=read();
        t1=read();
        t2=read();
        int u,v,l1,l2;
        init();
        while(m--){
            u=read();
            v=read();
            l1=read();
            l2=read();
            add(u,v,l1,l2);
            add(v,u,l1,l2);
        }
        int l=0,r=t0+1;
        while(l<=r){
            int mid=l+r>>1;
            if(dijkstra(1,mid))l=mid+1;
            else r=mid-1;
        }
        printf("%d\n",r);
        //二分
    }
    return 0;
}

题解：CF2000G Call During the Journey

文章操作