1 条题解
-
0
题意简述
每条线路是可双向上下车的一组站点;求从站点 到站点 的最少换乘次数(上车的第一条线路不计),不可达输出 。
思路
关键转化:
"换乘"发生在两条线路之间,直接以"换乘次数"为距离不好转移。注意:
换乘次数 = 乘坐的线路数
于是问题变成:从站点 1 到站点 n 最少要乘坐多少条线路。若到达 至少要坐 条线路,答案就是 。
BFS:
把距离定义在站点上:
dist[s]= 从 到 最少乘坐的线路数,dist[1] = 0。转移:已用 条线路到达站点 ,那么 所在的每条还没坐过的线路 ,都能把 上的全部站点以 条线路到达(坐 本身不算换乘,但 计为新乘坐的一条线路)。而坐已经坐过的线路不会更优——它当初被触达时,它的所有站点已经以某个不超过当前值的距离入过队了。
于是做 BFS,队列里放站点:
- 弹出站点 ;
- 对 所在的每条未标记线路 :打标记,把 上所有
dist为 的站点置为dist[u] + 1并入队; - 队列空后,答案为:若
dist[n] = -1则 ,否则dist[n] - 1。
为什么每条线路只需展开一次:BFS 按
dist非降出队,一条线路第一次被触发时,触发它的站点是这条线路上dist最小的;之后再触发不可能更小。等价模型(用于对拍验证):在"线路图"(点 = 线路,两条线路共站即连边)上从"含站点 1 的线路"出发 BFS,层数即线路数,答案同样减 1。两个模型结论一致,互为正确性校验。
一个常见但不对的思路:
把同线任意两站当作单位边建"站点图"后跑普通 BFS,得到的是经过站点数最少,与换乘最少是两个不同目标(例:一条直达线跨 50 站、换乘 0 次;两条各乘 1 站换乘 1 次——按"站点数"前者更差,按"换乘数"前者更优)。若强行在状态里加入"当前所在线路",状态变成 (站点, 线路),规模乘 ,虽然也能过,但不如上面的刻度简洁。
复杂度
每条线路至多展开一次,摊还 ;总时间 ,空间同阶。、,轻松通过。
参考代码(C++)
#include <cstdio> #include <vector> #include <deque> using namespace std; int main() { freopen("bus.in", "r", stdin); freopen("bus.out", "w", stdout); int n, m; scanf("%d %d", &n, &m); vector<vector<int>> lineStops(m); vector<vector<int>> linesAt(n + 1); for (int i = 0; i < m; i++) { int k; scanf("%d", &k); lineStops[i].resize(k); for (int j = 0; j < k; j++) { scanf("%d", &lineStops[i][j]); linesAt[lineStops[i][j]].push_back(i); } } vector<int> dist(n + 1, -1); // dist[s]: 到达 s 最少乘坐的线路数 vector<bool> expanded(m, false); // 该线路是否已被展开 deque<int> q; dist[1] = 0; q.push_back(1); while (!q.empty()) { int u = q.front(); q.pop_front(); for (int L : linesAt[u]) { if (expanded[L]) continue; expanded[L] = true; for (int v : lineStops[L]) if (dist[v] == -1) { dist[v] = dist[u] + 1; q.push_back(v); } } } printf("%d\n", dist[n] == -1 ? -1 : dist[n] - 1); return 0; }易错点
- 忘减 1:样例 1 中
dist[n] = 3,输出 ;站点 1、 同线时dist[n] = 1,输出 。 - 不可达输出 :注意
dist[n] = -1既是哨兵又是答案,输出前判断即可,不要把哨兵当距离再减 1 变成 。 - 线路双向运行:不要按输入顺序当作有向线路。
- BFS 深度由线路数决定而不是站点数(测试点 10 是 500 条线路串成的链、换乘 499 次),手写循环队列时别按 估计大小;用递归 DFS 也会爆栈。
- 同一线路内站点互不相同是题目保证,不必去重;但"不重复乘坐一条线路"要靠线路标记实现,不能只靠站点标记。
测试点设计
测试点 设计意图 1–3 题面样例(答案 / / ) 4 最小规模 ,单条线路同时含 、 5 4 条线路链,答案 6 手工构造,答案 7 5 条线路全含站点 1 但都不含 : 8–9 随机(小 / 中) 10 , 条 长链:答案 ,卡队列开小 / 递归爆栈 11 、 满规模随机(已排除"某线同时含 与 "的平凡情形) 12 满规模随机连通图
- 1
信息
- ID
- 5
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 5
- 标签
- 递交数
- 2
- 已通过
- 2
- 上传者