【题解】P9751 [CSP-J 2023] 旅游巴士

· · 题解

传送门

题意简述

给一张有向无环图，求点 1 到达点 n 的最短时间，同时满足以下要求：

思路

说明：下文中所有的 u 和 v （边的起点与终点）均是从原图角度来说，而不是反图。

首先尝试正向思考。经过一条边需要考虑其是否到达开放时间，并且还要保证起点和终点时间必须为 k 的倍数，最短路可能并没有办法达到这个要求，dfs 耗时又巨大。正向思考难度较大，暂时放弃。

如果我们考虑建反图，题目就变成了求 n 点到 1 点的最短时间，乍一看没什么变化，但之前困扰我们的“开放时间”就没有这么难了。本来，通过一条边必须要满足 dis[u]>=w 这一条件，但这是最长路更新的条件，和我们求的最短时间相违背；建反图后，这个条件就变成了 dis[u]<=w 时可以通过，和求最短路的更新条件相同，于是我们就可以放心跑最短路了。

还有一点，建反图之后我们可以发现，到达时间 t 是具有单调性的。假设 t_i 是一个合法的到达时间，那么比它大的时间必定能到达，而比 t_i 小的则不一定。因此，我们可以采用二分。二分什么呢？为了保证到达时间是 k 的倍数，我们可以二分 n \times k = arrivetime 之中的这个 n，即二分 k 的倍数。

接下来是建图。为了保证到达 1 号点时的时间也为 k 的倍数，我们走过的路的长度必须也为 k 的倍数。考虑拆点，将一个点拆成 k 个点，表示到达该点时的已经走过的路径长度 mod k。建图时，我们需要将 v 的第 x-1 层连接到 u 的第 x 层，将 v 的第 k-1 层连接到 u 的第 0 层，表示走过的路径长度加一后对 k 取模。最后我们只需要检查 1 号点的状态有没有被更新即可（1 号点是起点，能抵达 1 号点，说明走过的路径长度一定是 k 的倍数）。

建好图后，二分倍数，check 函数用 bfs 代替即可。

（意即：用 bfs 判断能否按照题目要求从 n 号点走到 1 号点。当然，跑最短路也是可以的）

注意事项

该做法时间复杂度较高，数组的大小和二分的范围均决定了分数大小。

经过反复测试后，发现数组大小在 1900000 比较合适，二分范围在 0~1800000 比较合适，能够通过此题。

代码


#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 1900000;
const int inf = 2e9;

int n,m,k,t,ans,cnt=1;

int dis[N],head[N],vis[N];

struct edge{
    int to,next,w;
}e[N];

void add(int u,int v,int w) {
    e[++cnt].next=head[u];
    head[u]=cnt;
    e[cnt].to=v; e[cnt].w=w;
}

inline int read() {
    int s=0,w=1; char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-') w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') {s=s*10+ch-'0';ch=getchar();}
    return s*w;
}

void print(int x)
{
    if(x<0)
        putchar('-'),x=-x;
    if(x>9)
        print(x/10);
    putchar(x%10+'0');
    return;
}

void init() {
    for(int i=0;i<n*k;++i) vis[i]=0,dis[i]=inf;
}

bool bfs(int x) {
    init();
    queue<int> q;
    q.push(n); 
    vis[n]=1; dis[n]=x*k;
    while(q.size()) {
        int u = q.front(); q.pop();
        for(int i=head[u];i;i=e[i].next) {
            int v = e[i].to,w = e[i].w;
            if(dis[u]>w&&dis[v]==inf) {
                dis[v]=dis[u]-1;
                if(v==1) return 1;
                if(vis[v]==0) {
                    vis[v]=1; q.push(v);
                }
            }
        } 
    }
    if(dis[1]==inf) return 0;
    return 1;
}
void solve() {
    n=read(); m=read(); k=read();
    for(int i=1,u,v,w;i<=m;++i) {
        u=read(); v=read(); w=read();
        for(int j=1;j<k;++j) {
            add(v+(j-1)*n,u+j*n,w);
        }
        add(v+n*(k-1),u,w);
    }
    int l=0,r=1800000;
    while(l<r) {
        int mid = l+r >> 1;
        if(bfs(mid)) r=mid;
        else l=mid+1;
    }
    int tmp = bfs(l);
    if(dis[1]==inf) {
        print(-1); return ;
    }
    print(l*k);
}

int main(){
    ios::sync_with_stdio(0);
    solve();
    return 0;
}