把线路 i 的位置 j 看成相位固定的班次,等车时刻为 d+((j-d) mod t_i),在站台图上按“早到不劣”跑 Dijkstra,边权松弛时实时算、不显式建图。
OJ: roj
题目 ID: 1715
难度:提高
标签:图论最短路Dijkstrapython
创建: 2026-10-07 18:13
更新: 2026-10-07 18:13
形式化题目
有
正解
思路
先把“车”改写成“相位固定的班次”。 车
关键观察:早到永远不会更差。 我若在
等车时刻怎么算。 设我在
(取非负余数,即
为什么可以套 Dijkstra,而不必把图建出来。 普通边权最短路要求边权固定;这里的“边权”是
不建图的实现。 显式建图要对每个站台的每一条出边存相位与周期,而且边权还得在松弛时重算,不如直接预处理出“每个站台上出现过哪些(线路号,线路内位置)对”,Dijkstra 弹出一个站台
下面用题面样例重演前几步(
| 当前站台(最早时刻 |
可搭的班次(位置 |
等到 |
到达 |
|---|---|---|---|
| 线路 |
站台 |
||
| 线路 |
站台 |
||
| 线路 |
站台 |
||
| 线路 |
站台 |
||
| 线路 |
站台 |
得到 2 3 4 6 3 -1 -1 一致。
实现上有两个易错点:
- 余数必须取非负。 C++ 里
(j - d) % t_i当时为负,要写成 ((j - d) % t_i + t_i) % t_i;Python 的%天然非负,可直接写(j - d) % t_i。 dist要用 64 位。 每跳最多等个时刻,总时刻上界约 ,超过 int,long long与 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()/**
* 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;
}复杂度
设
按题面数据范围 heapq + 站台分桶)实测最大测例约
总结
本题的难点不在最短路模板,而在把“随时间移动的公交车”翻译成“相位固定的边”:车
图示解析
相位与等待
下图画出样例中线路
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"]
观察重点:同一辆车的周期表里,每个站台出现的位置决定了我能等到它的时刻。若我
说明
本题素材源带数据生成脚本(data.py,cyaron),data/ 的 std.cpp 与题面模型一致,已用这 main.cpp 按上述推导独立重写,与 std.cpp 输出逐点一致,并额外用一份“按时间正向推进的 BFS”暴力在