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

· · 题解

这题如果啥都不会，千万别忘了输出 -1 祈求 CCF 的施舍，能骗多少分就看缘分了

注意到 k\le 100，显然是一个分层图问题，即图上每个点要拆分成 k 个状态。

对所有满足特殊性质 a_i=0 的点，没有时间限制，那肯定是 0 时刻来到起点啊。直接在分层图上用 BFS 跑最短路即可，这样就有 35 分啦！

具体地，设 d_{i,j} 表示到 i 这个点满足时间 \bmod k=j 的最短时间，初始 d_{1,0}=0，目标求 d_{n,0}，参考代码如下：

vector<pair<int, int>> G[N];
int d[N][105];
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, -1, sizeof d);
    queue<pair<int, int>> q;
    d[1][0] = 0;
    q.push({1, 0});
    while (q.size()) {
        auto [u, i] = q.front();
        q.pop();
        for (auto [v, w] : G[u]) {
            int j = (i + 1) % kk;
            if (d[v][j] == -1) {
                d[v][j] = d[u][i] + 1;
                q.push({v, j});
            }
        }
    }
    printf("%d\n", d[n][0]);
    return 0;
}

每条边有了时间限制，其实也不用怕，可以原地等待 k 的倍数时间来达到这个限制，等价于起点的出发时间往后偏移了这么多。

比如当前的边需要的时间是 w 大于目前时间 t ，那么就需要让出发时间延后 \lceil {w -t\over k} \rceil \cdot k 单位时间。

然后这样普通 BFS 就不行了，得用优先队列来贪心选取当前最小状态来拓展，本质上就是 Dijkstra 算法。

时间复杂度 O(nk\log nk)，完整代码如下：

#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];
int vis[N][105];
struct Node {
    int u, i, 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()) {
        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]) {
            int t = d[u][i], j = (i + 1) % kk;
            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});
        }
    }
    if (d[n][0] == INF) d[n][0] = -1;
    printf("%d\n", d[n][0]);
    return 0;
}