2023 旅游巴士 · 方案一分层图加优先队列

CSP-J 标程 · 复赛真题 · 代码 · cpp · 难度 4/5 · 共 2216 字

状态记成点与时刻对 k 取余

2023
图论

正文

// CSP-J 2023 复赛 T4 · 旅游巴士
// 原题：https://oj.yecheng.tv/p/CSPJ2023D
// 题意：有向图，每条边 (u, v, a) 只能在「不早于 a 时刻」通过，通过耗时 1。
// 每 k 个单位时间有一班巴士到入口、一班从出口离开。
// 到达和离开的时刻都必须是 k 的倍数，而且全程不能在任何地方停留。
// 问最早能在什么时刻离开，无解输出 -1。
//
// 方案一 · 分层图最短路（优先队列 Dijkstra）
// 突破口是「不能停留」+「入口时刻必须是 k 的倍数」：
// 一旦选定出发时刻，路径上每一步的时刻就完全定死了；
// 而把出发时刻往后推 k 的整数倍，路上每一步的时刻也整体后移 k 的整数倍 ——
// 也就是说，真正影响「能不能走这条边」的只有「当前时刻除以 k 的余数」。
// 于是把状态记成 (点 u, 到达 u 的时刻 mod k)，一共 n * k 个：
//   dis[u][r] = 到达 u、且时刻 mod k 等于 r 的最早时刻。
// 走一条边 (u, v, a) 时：当前最早时刻是 t = dis[u][r]，
//   若 t < a，就把出发时刻整体后推若干个 k，直到 t >= a 且 t mod k 仍是 r；
//   然后到达 v 的时刻是 t + 1，余数变成 (r + 1) mod k。
// 用优先队列每次取时刻最小的状态来松弛（时刻只会越来越大，所以 Dijkstra 成立）。
// 答案就是 dis[n][0]：到达出口的时刻正好是 k 的倍数，可以直接上车走人。

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 10005;
const int MAXK = 105;
const long long INF = (1LL << 60);

struct Edge {
    int to;
    long long open;      // 这条边的开放时刻
};

vector<Edge> g[MAXN];
long long dis[MAXN][MAXK];

struct State {
    long long t;
    int u;
    int r;
    bool operator>(const State& o) const { return t > o.t; }
};

int main() {
    freopen("bus.in", "r", stdin);
    freopen("bus.out", "w", stdout);

    int n, m, k;
    cin >> n >> m >> k;
    for (int i = 0; i < m; i++) {
        int u, v;
        long long a;
        cin >> u >> v >> a;
        g[u].push_back({v, a});
    }

    for (int u = 1; u <= n; u++) {
        for (int r = 0; r < k; r++) dis[u][r] = INF;
    }
    dis[1][0] = 0;
    priority_queue<State, vector<State>, greater<State>> pq;
    pq.push({0, 1, 0});

    while (!pq.empty()) {
        State cur = pq.top();
        pq.pop();
        if (cur.t != dis[cur.u][cur.r]) continue;
        for (const Edge& e : g[cur.u]) {
            long long t = cur.t;
            if (t < e.open) {
                long long add = (e.open - t + k - 1) / k * k;   // 整体后推整数个 k
                t += add;
            }
            long long arrive = t + 1;
            int nr = (cur.r + 1) % k;
            if (arrive < dis[e.to][nr]) {
                dis[e.to][nr] = arrive;
                pq.push({arrive, e.to, nr});
            }
        }
    }

    if (dis[n][0] == INF) cout << -1 << "\n";
    else cout << dis[n][0] << "\n";
    return 0;
}

2023 旅游巴士 · 方案一 分层图加优先队列

正文

CSP-J 标程 · 复赛真题的其它内容

2023 旅游巴士 · 方案一分层图加优先队列