2023 旅游巴士 · 方案二状态压成一维

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

用队列松弛，编号压成 u 乘 k 加 r

2023
图论

正文

// CSP-J 2023 复赛 T4 · 旅游巴士（方案二）
// 原题：https://oj.yecheng.tv/p/CSPJ2023D
//
// 方案二 · 状态压成一维 + 队列松弛（SPFA 写法）
// 思路与方案一完全相同，两处代码上的不同：
//   1. 把二维状态 (u, r) 压成一个整数编号 u * k + r，用一个一维 dis 数组存，
//      取用的时候再拆开，省掉二维数组的下标换算；
//   2. 松弛改用普通队列（SPFA）：哪个状态被更新了就重新入队继续松弛，
//      写法比优先队列短。因为这里的转移是「时刻只会往前走」，
//      用优先队列的 Dijkstra 复杂度更稳，竞赛里更推荐方案一那一版。
// 两者都建立在同一个关键观察上：出发时刻往后挪 k 的整数倍，
// 路上每一步的时刻也整体挪 k 的整数倍，所以只需要记「时刻 mod 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];
bool inq[MAXN * MAXK];

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});
    }

    int total = (n + 1) * k;
    for (int i = 0; i < total; i++) dis[i] = INF;

    int start = 1 * k + 0;
    dis[start] = 0;
    queue<int> q;
    q.push(start);
    inq[start] = true;

    while (!q.empty()) {
        int id = q.front();
        q.pop();
        inq[id] = false;
        int u = id / k;
        int r = id % k;
        for (const Edge& e : g[u]) {
            long long t = dis[id];
            if (t < e.open) t += (e.open - t + k - 1) / k * k;   // 等到这条边开放
            long long arrive = t + 1;
            int nr = (r + 1) % k;
            int nid = e.to * k + nr;
            if (arrive < dis[nid]) {
                dis[nid] = arrive;
                if (!inq[nid]) {
                    q.push(nid);
                    inq[nid] = true;
                }
            }
        }
    }

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

2023 旅游巴士 · 方案二 状态压成一维

正文

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

2023 旅游巴士 · 方案二状态压成一维