公交旅行

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

把线路 i 的位置 j 看成相位固定的班次,等车时刻为 d+((j-d) mod t_i),在站台图上按“早到不劣”跑 Dijkstra,边权松弛时实时算、不显式建图。

OJ: roj

题目 ID: 1715

难度:提高

标签:图论最短路Dijkstrapython

创建: 2026-10-07 18:13

更新: 2026-10-07 18:13

形式化题目

有 nn 个站台和 mm 条环形公交线路。第 ii 条线路长度 ti⩾2t_i \geqslant 2,站台序列为 si,1,si,2,…,si,tis_{i,1}, s_{i,2}, \dots, s_{i,t_i}(同一站台可在一条线路中重复出现,但不会相邻)。00 时刻第 ii 辆车位于 si,1s_{i,1},之后每个时刻驶向序列中的下一个站台,到达末站后的下一个时刻回到始发站,即车 ii 在时刻 TT 位于位置

j=(T mod ti)+1(下标从 1 起)j = (T \bmod t_i) + 1 \quad(\text{下标从 } 1 \text{ 起})

00 时刻我在站台 11。若某时刻我与某辆车同处一个站台,我即可上车,并可在任意时刻下车,上下车不耗时;一次只能乘坐一辆车,但可以任意换乘。求最早到达站台 2,3,…,n2, 3, \dots, n 的时刻,不可达输出 −1-1。

正解

思路

先把“车”改写成“相位固定的班次”。 车 ii 在时刻 TT 位于位置 j=T mod tij = T \bmod t_i(改用 00 起下标),也就是说:位置 jj 这个站台只在时刻 T≡j(modti)T \equiv j \pmod{t_i} 时才有这班车停靠。于是每条线路的相邻两站 si[j]→si[(j+1) mod ti]s_i[j] \to s_i[(j+1) \bmod t_i] 构成一条“开放相位为 jj、周期为 tit_i”的道路,坐一站固定花 11 个时刻。

关键观察:早到永远不会更差。 我若在 dd 时刻就站在站台 vv,那么我可以在 vv 一直等到任何更晚的时刻再上车——等车不要钱。所以“到达某站台的时刻”这个量越小,我能接上的车只会更多,不会更少。于是每个站台只需要保留最早到达时刻 dist[v]\mathrm{dist}[v],这就是一个最短路问题。

等车时刻怎么算。 设我在 dd 时刻位于站台 v=si[j]v = s_i[j],想坐线路 ii 往下一站走。我必须等到该位置下一次“开门”:

T=d+((j−d) mod ti)T = d + \bigl((j - d) \bmod t_i\bigr)

(取非负余数,即 ((j−d) mod ti+ti) mod ti((j - d) \bmod t_i + t_i) \bmod t_i。)若 T=dT = d,说明车此刻正好停在这里,立刻上车。上车后再花 11 个时刻,于 T+1T + 1 到达 si[(j+1) mod ti]s_i[(j+1) \bmod t_i]。所以从 vv 出发、经由线路 ii 的这一次松弛给出

dist[si[(j+1) mod ti]]←min⁡(⋅, T+1)\mathrm{dist}\bigl[s_i[(j+1) \bmod t_i]\bigr] \gets \min\bigl(\cdot,\ T + 1\bigr)

为什么可以套 Dijkstra,而不必把图建出来。 普通边权最短路要求边权固定;这里的“边权”是 T+1−d=((j−d) mod ti)+1T + 1 - d = \bigl((j-d) \bmod t_i\bigr) + 1,随出发时刻 dd 而变。但由“早到不劣”可知:以 dist[v]\mathrm{dist}[v] 为出发时刻算出的到达时刻,一定不劣于用任何更晚出发时刻算出的结果。因此把 dist\mathrm{dist} 当作松弛用的标号,Dijkstra 的贪心仍然成立——每次弹出堆顶(当前最早可到达的站台)时,它的标号已经是最优的,用这个最优时刻去松弛别人只会得到正确(或更优)的结果。

不建图的实现。 显式建图要对每个站台的每一条出边存相位与周期,而且边权还得在松弛时重算,不如直接预处理出“每个站台上出现过哪些(线路号,线路内位置)对”,Dijkstra 弹出一个站台 vv 时,遍历这张表实时算 TT 与下一站即可。因为每个 (线路号, 位置) 只属于一个站台,总条目数恰为 ∑ti\sum t_i,所以复杂度与显式建图同阶。

下面用题面样例重演前几步(00 时刻我在站台 11):

当前站台(最早时刻 dd) 可搭的班次(位置 jj,周期 tit_i) 等到 TT 到达
11(d=0d=0) 线路 22 的 j=2j=2,t=3t=3(11 在 t≡2t \equiv 2) T=0+2=2T = 0 + 2 = 2 站台 22,时刻 22
11(d=0d=0) 线路 33 的 j=3j=3,t=4t=4(11 在 t≡3t \equiv 3) T=0+3=3T = 0 + 3 = 3 站台 33,时刻 33
22(d=2d=2) 线路 22 的 j=3j=3,t=3t=3(22 在 t≡3t \equiv 3) T=2T = 2,车正好在此 站台 66,时刻 33
33(d=3d=3) 线路 33 的 j=4j=4,t=4t=4(33 在 t≡4t \equiv 4) T=3T = 3,车正好在此 站台 44,时刻 44
44(d=4d=4) 线路 11 的 j=2j=2,t=2t=2(44 在 t≡2t \equiv 2) T=4+1=5T = 4 + 1 = 5 站台 55,时刻 66

得到 dist=(2,3,4,6,3)\mathrm{dist} = (2, 3, 4, 6, 3),站台 7,87, 8 从未出现在任何可达路径上,输出 −1-1,与样例 2 3 4 6 3 -1 -1 一致。

实现上有两个易错点:

  1. 余数必须取非负。 C++ 里 (j - d) % t_i 当 j<dj < d 时为负,要写成 ((j - d) % t_i + t_i) % t_i;Python 的 % 天然非负,可直接写 (j - d) % t_i。
  2. dist 要用 64 位。 每跳最多等 ti−1t_i - 1 个时刻,总时刻上界约 n⋅∑ti≈105×2×105=2×1010n \cdot \sum t_i \approx 10^5 \times 2 \times 10^5 = 2 \times 10^{10},超过 int,long long 与 Python 大整数都没问题。

代码

python
#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-07 18:13
# update_at: 2026-10-07 18:13

import heapq
import sys
from collections.abc import Iterator

INF = 1 << 62  # 不可达哨兵:大于任何可能到达时刻(n · Σt_i ≤ 2e10)

# 类型别名(Python 3.12+ 的 type 语句),相当于 C++ 的 using / typedef
type Routes = list[list[int]]             # 每条线路的站台序列,环长 = 周期 len(route)
type Stops = list[list[tuple[int, int]]]  # 站台 -> [(线路号, 该站台在线路中的位置)]


def read_input(data: Iterator[int]) -> tuple[int, Routes, Stops]:
    """读入 n、m 与 m 条线路,同时把每个 (线路号, 位置) 登记到它所在站台名下。"""
    n, m = next(data), next(data)
    routes: Routes = []
    stops: Stops = [[] for _ in range(n + 1)]
    for r in range(m):
        length = next(data)  # 题面的 t_i
        route = [next(data) for _ in range(length)]
        routes.append(route)
        for p, v in enumerate(route):
            stops[v].append((r, p))
    return n, routes, stops


def earliest_arrival(n: int, routes: Routes, stops: Stops) -> list[int]:
    """Dijkstra:dist[v] = 最早到达站台 v 的时刻,边权(等车 + 坐一站)松弛时实时算。"""
    dist = [INF] * (n + 1)
    dist[1] = 0
    done = [False] * (n + 1)
    heap = [(0, 1)]
    while heap:
        d, v = heapq.heappop(heap)
        if done[v]:
            continue
        done[v] = True
        for r, p in stops[v]:
            route = routes[r]
            period = len(route)
            # 车只在时刻 ≡ p (mod period) 停在 s_i[p]:等到相位 p 上车,1 个时刻后到下一站
            board = d + (p - d) % period
            nxt = route[(p + 1) % period]
            if board + 1 < dist[nxt]:
                dist[nxt] = board + 1
                heapq.heappush(heap, (board + 1, nxt))
    return dist


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n, routes, stops = read_input(data)
    dist = earliest_arrival(n, routes, stops)
    print(' '.join('-1' if dist[v] >= INF else str(dist[v]) for v in range(2, n + 1)))


if __name__ == "__main__":
    solve()
cpp
/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-07 18:13
 * update_at: 2026-10-07 18:13
 */
// ROJ 1715《公交旅行》
//
// 题意:n 个站台、m 条环形公交线路。第 i 条线路长 t_i,0 时刻第 i 辆车在 s_i[1],
//   之后每时刻开到线路里的下一站,到终点后下一时刻回到起点(位置按 (j+1) mod t_i 循环)。
//   0 时刻我在站台 1,与某辆车同处一站即可上车、任意时刻可下车,上下车不耗时,
//   一次只能坐一辆车但可换乘。求最早到达站台 2..n 的时刻,不可达输出 -1。
//
// 建模:线路 i 的车只在时刻 T ≡ j (mod t_i) 出现在站台 s_i[j](下标 0 起)。
//   若我在 d 时刻位于站台 s_i[j],最早可于 T = d + ((j - d) mod t_i) 上车,
//   T+1 时刻到达 s_i[(j+1) mod t_i]。由于"早到不会更差"(多等不花代价),
//   在站台图上跑 Dijkstra 即可,边权在松弛时实时计算、不必显式建图。
//
// 复杂度:时间 O(Σt_i · log n),空间 O(n + Σt_i)。

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

typedef long long ll;

static const ll INF = (ll)4e18;  // 大于任何可能到达时刻

// ---------- 快速读入 ----------
static char ibuf[1 << 22];
static int ilen = 0, ipos = 0;

static inline int gc() {
    if (ipos == ilen) {
        ilen = (int)fread(ibuf, 1, sizeof(ibuf), stdin);
        ipos = 0;
        if (ilen == 0) return -1;
    }
    return ibuf[ipos++];
}

static inline int readInt() {
    int c = gc();
    while (c != -1 && (c < '0' || c > '9')) c = gc();
    int x = 0;
    while (c >= '0' && c <= '9') {
        x = x * 10 + (c - '0');
        c = gc();
    }
    return x;
}

int n, m;                    // 站台数、线路数
vector<int> per;             // per[i] = t_i,线路 i 的周期(也是线路长度)
vector<int> off;             // off[i] = 线路 i 在 pool 中的起始下标
vector<int> pool;            // 所有线路的站台顺序拼接

vector<int> head;            // 站台 v 的邻接表起点(CSR)
vector<int> entR, entP;      // 每个 (线路号, 线路内位置) 条目

vector<ll> dist;             // dist[v] = 最早到达站台 v 的时刻
vector<char> done;

// 把站台 v 上出现的所有 (线路号, 位置) 建成 CSR 邻接表
void buildAt() {
    head.assign(n + 2, 0);
    for (size_t k = 0; k < pool.size(); k++) head[pool[k] + 1]++;
    for (int v = 1; v <= n; v++) head[v + 1] += head[v];
    vector<int> cur(head.begin(), head.end());
    entR.assign(pool.size(), 0);
    entP.assign(pool.size(), 0);
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < per[i]; j++) {
            int v = pool[off[i] + j];
            int slot = cur[v]++;
            entR[slot] = i;
            entP[slot] = j;
        }
    }
}

// 站台图上的 Dijkstra:边权(等车 + 坐一站)在松弛时按相位实时算
void dijkstra() {
    dist.assign(n + 1, INF);
    done.assign(n + 1, 0);
    dist[1] = 0;
    priority_queue<pair<ll, int>, vector<pair<ll, int> >, greater<pair<ll, int> > > pq;
    pq.push(make_pair((ll)0, 1));
    while (!pq.empty()) {
        pair<ll, int> top = pq.top();
        pq.pop();
        ll d = top.first;
        int v = top.second;
        if (done[v]) continue;
        done[v] = 1;
        for (int k = head[v]; k < head[v + 1]; k++) {
            int r = entR[k], p = entP[k];
            int t = per[r];
            ll board = d + (ll)((p - d) % t + t) % t;  // 等到相位 p 的最早时刻
            int nxt = pool[off[r] + (p + 1) % t];      // 再坐一站到的地方
            if (board + 1 < dist[nxt]) {
                dist[nxt] = board + 1;
                pq.push(make_pair(dist[nxt], nxt));
            }
        }
    }
}

int main() {
    n = readInt();
    m = readInt();
    per.resize(m);
    off.resize(m);
    pool.reserve(2 << 18);
    for (int i = 0; i < m; i++) {
        int ti = readInt();
        per[i] = ti;
        off[i] = (int)pool.size();
        for (int j = 0; j < ti; j++) pool.push_back(readInt());
    }
    buildAt();
    dijkstra();
    // 输出站台 2..n 的最早到达时刻,不可达输出 -1
    for (int v = 2; v <= n; v++) {
        if (v > 2) putchar(' ');
        if (dist[v] >= INF) fputs("-1", stdout);
        else printf("%lld", dist[v]);
    }
    putchar('\n');
    return 0;
}

复杂度

设 Σ=∑iti\Sigma = \sum_i t_i。预处理把每个 (线路号, 位置) 对挂到站台上:O(n+Σ)O(n + \Sigma)。Dijkstra 中每个站台出堆一次,每条条目被扫描至多一次,每次入堆 O(log⁡n)O(\log n),故时间 O(Σlog⁡n)O(\Sigma \log n),空间 O(n+Σ)O(n + \Sigma)。

按题面数据范围 n,m⩽105n, m \leqslant 10^5、Σ⩽2×105\Sigma \leqslant 2 \times 10^5:C++ 实现实测最大测例约 0.020.02 s;Python 实现(heapq + 站台分桶)实测最大测例约 0.240.24 s。

总结

本题的难点不在最短路模板,而在把“随时间移动的公交车”翻译成“相位固定的边”:车 ii 的位置 jj 只在时刻 ≡j(modti)\equiv j \pmod{t_i} 开门,于是“坐一站”的代价是“等到相位 jj”的等待量 ((j−d) mod ti)+1((j - d) \bmod t_i) + 1。第二个支点是早到不劣:既然等待免费,到达时刻就是唯一的标号,任何更晚到达都不会带来更多机会。有了这条单调性,即使边权依赖出发时刻,Dijkstra 的贪心依然成立,边权可以在松弛时现算,不需要把“时刻 × 站台”的时间展开图建出来(那会是 O(Σ⋅lcm)O(\Sigma \cdot \text{lcm}) 级别的爆炸)。把站台分桶成 (线路号, 位置) 列表后,每个条目只被扫描一次,总复杂度与显式建图同阶。

图示解析

相位与等待

下图画出样例中线路 22(周期 t=3t=3)的相位表:横轴是时刻,每一列写该时刻车所在的站台;我 00 时刻在站台 11,要坐车只能等到 t≡1(mod3)t \equiv 1 \pmod 3(站台 11 是位置 11),即 T=1T = 1,随后 T=2T = 2 到达站台 22。

flowchart LR
    T0["t=0<br/>站台 6"] --> T1["t=1<br/>站台 1"] --> T2["t=2<br/>站台 2"] --> T3["t=3<br/>站台 6"] --> T4["t=4<br/>站台 1"]

观察重点:同一辆车的周期表里,每个站台出现的位置决定了我能等到它的时刻。若我 dd 时刻才到站台 11(位置 11),就要等到 T=d+((1−d) mod 3)T = d + ((1 - d) \bmod 3);这正是“相位对齐”的代价,也是本题唯一需要小心取模的地方。

说明

本题素材源带数据生成脚本(data.py,cyaron),data/ 的 1010 组测试点是自造的,题面亦为网络重建(源自《信息学奥赛一本通 · 高手训练》图论部分),出题意图与官方原题可能存在偏差。素材源的 std.cpp 与题面模型一致,已用这 1010 组数据逐点验证通过;本篇 main.cpp 按上述推导独立重写,与 std.cpp 输出逐点一致,并额外用一份“按时间正向推进的 BFS”暴力在 300300 组小数据上对拍通过。