CSP-J（入门级）2023年T4 旅游巴士

小 Z 打算在国庆假期期间搭乘旅游巴士去一处他向往已久的景点旅游。旅游景点的地图共有n处地点，在这些地点之间连有m条道路。其中1号地点为景区入口，n号地点为景区出口。我们把一天当中景区开门营业的时间记为0时刻，则从0时刻起，每间隔k单位时间便有一辆旅游巴士到达景区入口，同时有一辆旅游巴士从景区出口驶离景区。所有道路均只能。对于每条道路，游客步行通过的用时均为恰好1单位时间。

长春高老师编程

2495人浏览 · 2023-10-26 13:28:17

长春高老师编程 · 2023-10-26 13:28:17 发布

[CSP-J 2023] 旅游巴士【民间数据】

题目描述

小 Z 打算在国庆假期期间搭乘旅游巴士去一处他向往已久的景点旅游。

旅游景点的地图共有 $n$ 处地点，在这些地点之间连有 $m$ 条道路。其中 $1$ 号地点为景区入口， $n$ 号地点为景区出口。我们把一天当中景区开门营业的时间记为 $0$ 时刻，则从 $0$ 时刻起，每间隔 $k$ 单位时间便有一辆旅游巴士到达景区入口，同时有一辆旅游巴士从景区出口驶离景区。

所有道路均只能单向通行。对于每条道路，游客步行通过的用时均为恰好 $1$ 单位时间。

小 Z 希望乘坐旅游巴士到达景区入口，并沿着自己选择的任意路径走到景区出口，再乘坐旅游巴士离开，这意味着他到达和离开景区的时间都必须是 $k$ 的非负整数倍。由于节假日客流众多，小 Z 在旅游巴士离开景区前只想一直沿着景区道路移动，而不想在任何地点（包括景区入口和出口）或者道路上停留。

出发前，小 Z 忽然得知：景区采取了限制客流的方法，对于每条道路均设置了一个
“开放时间” $a _ i$ ，游客只有不早于 $a _ i$ 时刻才能通过这条道路。

请帮助小 Z 设计一个旅游方案，使得他乘坐旅游巴士离开景区的时间尽量地早。

输入格式

输入的第一行包含 3 个正整数 $n, m, k$ ，表示旅游景点的地点数、道路数，以及旅游巴士的发车间隔。

输入的接下来 $m$ 行，每行包含 3 个非负整数 $u _ i, v _ i, a_ i$ ，表示第 $i$ 条道路从地点 $u _ i$ 出发，到达地点 $v _ i$ ，道路的“开放时间”为 $a _ i$ 。

输出格式

输出一行，仅包含一个整数，表示小 Z 最早乘坐旅游巴士离开景区的时刻。如果不存在符合要求的旅游方案，输出 -1。

样例 #1

样例输入 #1

样例输出 #1

提示

【样例 #1 解释】

小 Z 可以在 $3$ 时刻到达景区入口，沿 $\to 3 \to 4 \to 5$ 的顺序走到景区出口，并在 $6$ 时刻离开。

【样例 #2】

见附件中的 bus/bus2.in 与 bus/bus2.ans。

【数据范围】

对于所有测试数据有： $\leq n \leq 10 ^ 4$ ， $\leq m \leq 2 \times 10 ^ 4$ ， $\leq k \leq 100$ ， $\leq u _ i, v _ i \leq n$ ， $\leq a _ i \leq 10 ^ 6$ 。

测试点编号	$\leq$	$\leq$	$\leq$	特殊性质
$\sim 2$	$10$	$15$	$100$	$a _ i = 0$
$\sim 5$	$10$	$15$	$100$	无
$\sim 7$	$10 ^ 4$	$\times 10 ^ 4$	$1$	$a _ i = 0$
$\sim 10$	$10 ^ 4$	$\times 10 ^ 4$	$1$	无
$\sim 13$	$10 ^ 4$	$\times 10 ^ 4$	$100$	$a _ i = 0$
$\sim 15$	$10 ^ 4$	$\times 10 ^ 4$	$100$	$\leq v _ i$
$\sim 20$	$10 ^ 4$	$\times 10 ^ 4$	$100$	无

【解析】
使用优先队列保存当前到达的景点及到达时间，BFS搜索，直至找到到达终点，且时间是k的倍数。悲催的是只有5分o(╥﹏╥)o。
详见代码：

#include <bits/stdc++.h>
using namespace std;
int n,m,k;
int ans=0;
vector <int> to[10005];//目标景点
vector <int> a[10005];//开通时间
struct node{
    int d;//目前景点
    int t;//目前时间
    bool operator < (const node &a) const{//重载运算符，时间靠前的排在前面
        return t>a.t;
    }
};
priority_queue<node> pq;//优先队列，时间靠前的排在前面
void bfs(){
    node tmp;
    tmp.d=1;
    tmp.t=0;
    pq.push(tmp);//起点入队
    while (!pq.empty()){
        if (ans!=0){//如果找到答案
            break;
        }
        tmp=pq.top();
        pq.pop();
        int from=tmp.d;//出发景点
        int tx=tmp.t;//出发时间
        if(tx>1100000){//超时退出
            break;
        }
        if (from==n&&tx%k==0){//如果当前是出口，且时间是k的倍数，找到答案
            ans=tx;
            break;
        }
        for (int i=0;i<to[from].size();i++){
            node next;
            next.d=to[from][i];
            if (a[from][i]<=tx){//如果该道路已经开放
                next.t=tx+1;
            }else{//如果该道路没有开放
                int cha=a[from][i]-tx;//还差cha时间开放
                next.t=tx+1+(cha+k-1)/k*k;//晚到入口（差值除k向上取整倍k）
            }
            pq.push(next);//下一景点入队
        }
    }
}
main() {
    scanf("%d%d%d",&n,&m,&k);
    for(int i=1;i<=m;i++){
        int u,v,x;
        scanf("%d%d%d",&u,&v,&x);//vector邻接表存边
        to[u].push_back(v);
        a[u].push_back(x);
    }
    bfs();//广搜
    if (ans==0){//如果没有答案
        cout<<-1;
        return 0;
    }
    cout<<ans;//输出答案
    return 0;
}

感谢网友 code lin 提供的正解：
用优先队列来贪心选取当前最小状态来拓展，本质上就是 Dijkstra 算法。
时间复杂度：O(nk log nk):
简单解释一下，把所有景点扩展为k个点，用到达该景点时间t%k区别这k个点，然后对这n*k个点用dijkstra（迪杰斯特拉算法），使用优先队列优化找到最小蓝点的方法，详见代码

#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
const int N = 10005;
 
vector<pair<int, int>> G[N];//保存边的信息
int d[N][105];//保存最小时间d[i][j]表示到达景点i，时间模k为j的最小时间
int vis[N][105];//标记是否蓝点（参考dijkstra算法）
struct Node {//优先队列节点，时间短的靠前
    int u, i, d;//u,景点编号；i,时间模k的余数；d，最短时间
    bool operator<(const Node &rhs) const {
        return d > rhs.d;
    }
};
int main() {
    int n, m, kk;
    scanf("%d%d%d", &n, &m, &kk);
    while (m--) {
        int u, v, w;
        scanf("%d%d%d", &u, &v, &w);
        G[u].push_back({v, w});//邻接表存边
    }
    memset(d, 0x3f, sizeof d);//初始化最小距离
    priority_queue<Node> q;//优先队列
    q.push({1, 0, d[1][0] = 0});//起点入队
    while (q.size()) {//只要队列非空，继续
        //取当前最小白点（参考dijkstra）
        int u = q.top().u, i = q.top().i;
        q.pop();
        if (vis[u][i]) continue;//如果已经标记为蓝点，忽略
        vis[u][i] = 1;//标记为蓝点
        for (auto [v, w] : G[u]) {//枚举该节点的所有边
            //计算出发时间和到达时间模k的余数
            int t = d[u][i], j = (i + 1) % kk;
            //如果路线不通，延时k的整数倍时间，保证刚好通过不浪费时间
            if (t < w) t += (w - t + kk - 1) / kk * kk;
            //如果新时间比原来时间短，更新入队
            if (d[v][j] > t + 1) q.push({v, j, d[v][j] = t + 1});
        }
    }
    //如果不能到达，输出-1
    if (d[n][0] == INF) d[n][0] = -1;
    printf("%d\n", d[n][0]);
    return 0;
}