[CSP-J 2023] 旅游巴士

GitHub 跳转原题关系图返回列表

把状态设成 (点, 当前时刻 mod k)，在状态图上跑 Dijkstra，转移时把时间补到不早于开放时刻且同余不变的最早值。

OJ: luogu

题目 ID: P9751

难度:普及+/提高

标签:图论最短路状态压缩

日期: 2026-06-19 19:45

题意

给出一个有向图，边有开放时间。游客只能在时间是 k 的倍数时进出景区，进入后不能停留，只能一直沿边走，每条边要在不早于其开放时间时通过。

要求最早离开景区的时刻。

思路

最直接的办法是按时间模拟或者枚举起步时刻。

先看一个可以直接验证想法的朴素解：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62#include <bits/stdc++.h>
using namespace std;

struct Edge {
    int to;
    int open;
};

const long long INF = (1LL << 60);

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m, k;
    cin >> n >> m >> k;

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

    vector<vector<long long>> dist(n + 1, vector<long long>(k, INF));
    deque<pair<int, int>> q;
    vector<vector<int>> inq(n + 1, vector<int>(k, 0));
    dist[1][0] = 0;
    q.push_back({1, 0});
    inq[1][0] = 1;

    while (!q.empty()) {
        auto [u, mod] = q.front();
        q.pop_front();
        inq[u][mod] = 0;

        for (const auto &e : g[u]) {
            long long nd = dist[u][mod];
            if (nd < e.open) {
                long long delta = e.open - nd;
                long long t = (delta + k - 1) / k;
                nd += t * 1LL * k;
            }
            ++nd;
            int nmod = nd % k;
            if (nd < dist[e.to][nmod]) {
                dist[e.to][nmod] = nd;
                if (!inq[e.to][nmod]) {
                    inq[e.to][nmod] = 1;
                    q.push_back({e.to, nmod});
                }
            }
        }
    }

    if (dist[n][0] == INF) {
        cout << -1 << '\n';
    } else {
        cout << dist[n][0] << '\n';
    }
    return 0;
}

下面是另一种「状态搜索」风格的暴力写法。它从当前点和当前时刻出发，递归枚举下一条已经开放的边，只适合小数据观察状态变化：

另一种暴力写法：状态搜索

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71// brute_01_style.cpp：状态搜索风格暴力，枚举每一时刻走哪条边，只适合小数据。
#include <bits/stdc++.h>
using namespace std;

struct Edge {
    int to;
    int open;
};

const int MAXN = 105;
const int MAX_TIME = 500;
const long long INF = (1LL << 60);

int n, m, k;
vector<Edge> g[MAXN];
bool seen[MAXN][MAX_TIME + 5];
long long answer;

void dfs(int u, int time_now) {
    if (time_now > MAX_TIME || time_now >= answer) {
        return;
    }

    if (seen[u][time_now]) {
        return;
    }
    seen[u][time_now] = true;

    if (u == n && time_now % k == 0) {
        answer = min(answer, (long long)time_now);
        return;
    }

    // 当前层递归选择下一条要走的道路。不能等待，只能走已经开放的边。
    for (int i = 0; i < (int)g[u].size(); i++) {
        int v = g[u][i].to;
        int open_time = g[u][i].open;
        if (time_now < open_time) {
            continue;
        }
        dfs(v, time_now + 1);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

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

    answer = INF;

    // 枚举乘哪一班车到入口：出发时刻必须是 k 的倍数。
    for (int start = 0; start <= MAX_TIME; start += k) {
        memset(seen, 0, sizeof(seen));
        dfs(1, start);
    }

    if (answer == INF) {
        cout << -1 << '\n';
    } else {
        cout << answer << '\n';
    }

    return 0;
}

brute.cpp 在小图上直接按状态图做朴素松弛，适合对拍，但正式数据下还是应该用 Dijkstra。

关键观察是：虽然不能在图里原地等待，但我们可以把“乘坐入口巴士的时刻”整体往后推迟若干个 k。这样整条前缀路径上经过每条边的时刻都会同时增加 k 的倍数，所有时刻对 k 的余数保持不变。

因此状态只需要记录：

当前在哪个点
当前时刻对 k 的余数

这张图展示样例 1 的小图：

digraph G {
  1 -> 2 [label="0"];
  2 -> 5 [label="1"];
  1 -> 3 [label="0"];
  3 -> 4 [label="3"];
  4 -> 5 [label="1"];
}

从图里可以看出，虽然 1 -> 2 -> 5 路径更短，但它的总长度不是 $k=3$ 的倍数，不能直接作为最终方案；而 1 -> 3 -> 4 -> 5 长度正好是 3，只要把起步时刻推迟到 3，就能满足中间边 3 -> 4 的开放时间限制，最终在 6 时刻离开。

因此设 dist[u][r] 表示到达点 u 且当前时刻 $mod k = r$ 时的最早真实时刻。在状态 (u, r) 上走一条开放时间为 a 的边时，如果当前时刻还没到 a，就把真实时刻向上补到不早于 a 且余数仍为 r 的最早值，然后再走这条边。

最后答案就是 dist[n][0]，因为离开景区时刻也必须是 k 的倍数。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71#include <bits/stdc++.h>
using namespace std;

struct Edge {
    int to;
    int open;
};

struct Node {
    long long dist;
    int u;
    int mod;
    bool operator<(const Node &other) const {
        return dist > other.dist;
    }
};

const long long INF = (1LL << 60);

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m, k;
    cin >> n >> m >> k;

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

    vector<vector<long long>> dist(n + 1, vector<long long>(k, INF));
    priority_queue<Node> pq;
    dist[1][0] = 0;
    pq.push({0, 1, 0});

    while (!pq.empty()) {
        auto cur = pq.top();
        pq.pop();
        long long d = cur.dist;
        int u = cur.u;
        int mod = cur.mod;
        if (d != dist[u][mod]) {
            continue;
        }

        for (const auto &e : g[u]) {
            long long nd = d;
            if (nd < e.open) {
                long long delta = e.open - nd;
                long long t = (delta + k - 1) / k;
                nd += t * 1LL * k;
            }
            ++nd;
            int nmod = nd % k;
            if (nd < dist[e.to][nmod]) {
                dist[e.to][nmod] = nd;
                pq.push({nd, e.to, nmod});
            }
        }
    }

    if (dist[n][0] == INF) {
        cout << -1 << '\n';
    } else {
        cout << dist[n][0] << '\n';
    }
    return 0;
}

SPFA 风格

下面这份代码还是同一个状态定义和转移，只是把优先队列换成普通队列做松弛。它更接近“不断更新状态”的写法，适合和上面的 Dijkstra 版本对照理解；正式提交时，Dijkstra 版本的复杂度更稳定。

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91#include <bits/stdc++.h>
using namespace std;

struct Edge {
  int to;        // 终点
  int open_time; // 这条边最早可以通过的时刻
};

struct State {
  int vertex;    // 当前所在的点
  int remainder; // 当前时刻除以 k 的余数
};

const int maxn = 10005;
const long long INF = (1LL << 60);

long long dist[maxn][105];
bool in_queue[maxn][105];
int n, k;
vector<Edge> g[maxn];

// SPFA 在分层图（点 × 余数）上求最短路。
// 状态 (u, r) 表示：到达 u 且到达时刻 mod k = r。
// dist[u][r] 记录该状态的最早真实到达时刻。
void spfa() {
  // 初始化所有状态为 INF
  for (int i = 1; i <= n; ++i)
    for (int j = 0; j < k; ++j)
      dist[i][j] = INF;

  queue<State> q;
  // 入口：0 时刻乘车到达 1 号点，余数为 0
  dist[1][0] = 0;
  q.push({1, 0});
  in_queue[1][0] = true;

  while (!q.empty()) {
    State cur = q.front(); q.pop();
    int u = cur.vertex;
    int r = cur.remainder;
    in_queue[u][r] = false; // 出队标记

    for (int i = 0; i < (int)g[u].size(); ++i) {
      Edge &e = g[u][i];
      long long t = dist[u][r];

      // 如果当前时刻早于道路的开放时间，
      // 不能原地等待，只能把整条路径后移若干个 k（入口巴士推迟）
      if (t < e.open_time) {
        long long diff = e.open_time - t;
        long long p = (diff + k - 1) / k; // 需要推迟几个周期
        t += p * k;
      }

      // 每条道路恰好走 1 单位时间
      long long nt = t + 1;
      int nr = nt % k; // 下一状态的余数

      // 松弛：找到更早的到达时刻才更新
      if (nt >= dist[e.to][nr]) continue;
      dist[e.to][nr] = nt;

      // 如果不在队列中则入队，避免重复
      if (!in_queue[e.to][nr]) {
        q.push({e.to, nr});
        in_queue[e.to][nr] = true;
      }
    }
  }
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int m;
  cin >> n >> m >> k;

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

  spfa();

  if (dist[n][0] == INF) cout << -1 << '\n';
  else cout << dist[n][0] << '\n';

  return 0;
}

复杂度

状态数是 $n * k$ ，在状态图上跑 Dijkstra，总时间复杂度大致是 $O((n*k + m*k) log(n*k))$ ，空间复杂度是 $O(n*k + m)$ 。

总结

这题的关键不在于直接模拟时间，而在于抓住“起步时间可以整体延后 k 的倍数”这一点。把状态写成 (点, 时间 mod k) 后，就是一个标准的状态最短路。

一图流解析

这张图把本题的建模、关键转移、实现检查和训练方法压缩到一页，适合读完正文后复盘。

P9751 [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

text

输出 #1

text

说明/提示

【样例 #1 解释】

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

【样例 #2】

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

【数据范围】

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

测试点编号	$n \leq$	$m \leq$	$k \leq$	特殊性质
$1 \sim 2$	$10$	$15$	$100$	$a _ i = 0$
$3 \sim 5$	$10$	$15$	$100$	无
$6 \sim 7$	$10 ^ 4$	$2 \times 10 ^ 4$	$1$	$a _ i = 0$
$8 \sim 10$	$10 ^ 4$	$2 \times 10 ^ 4$	$1$	无
$11 \sim 13$	$10 ^ 4$	$2 \times 10 ^ 4$	$100$	$a _ i = 0$
$14 \sim 15$	$10 ^ 4$	$2 \times 10 ^ 4$	$100$	$u _ i \leq v _ i$
$16 \sim 20$	$10 ^ 4$	$2 \times 10 ^ 4$	$100$	无

[CSP-J 2023] 旅游巴士

目录

题意

思路

代码

SPFA 风格

复杂度

总结

一图流解析