题目链接
题目描述
有 条单向巴士线路与
个站点。第
条线路依次经过若干站点，方向与输入次序一致，旅客可在同一站点即时换乘到另一条线路。设站点编号为
，从
号站到
号站，最少需要换乘多少次？若无法到达，输出
；若无需换乘，换乘次数为
。
解题思路
-
建图思想（0-1 BFS）：
- 建立两类节点：
- 站点节点：
。
- 线路位置节点：对每条线路
的第
个站位建节点
（表示“在
- 站点节点：
- 加边规则：
- 登车：
（当该站位即为站点
），费用
（一次上车，对应一次“潜在换乘”）。
- 沿线前进：
，费用
（同一线路内前进不增加换乘）。
- 下车：
（该站位对应站点
- 登车：
- 从
出发，用 0-1 BFS 求到
的最小费用
。由于初次上车也计为一次“登车”，而题目只统计“换乘次数”，所以最终答案为：
- 建立两类节点：
-
正确性：同一线路内前进费用为
-
复杂度：设所有线路长度之和为
，节点数约为
，边数约为
，0-1 BFS 时间复杂度
，空间复杂度
代码
#include <bits/stdc++.h>
using namespace std;
using int64 = long long;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int L, N; // L: 线路数, N: 站点数（目标为从 1 到 N）
if (!(cin >> L >> N)) return 0;
// 记录每条线路经过的站点序列
vector<vector<int>> lineStops(L);
// 记录每条线路每个位置对应的节点编号（线路位置节点）
vector<vector<int>> posNodeId(L);
// 站点 -> 该站点出现的所有(线路, 位置) 列表
vector<vector<pair<int,int>>> stationOccur(N + 1);
// 预留节点编号：前 N 个留给站点节点 S_1..S_N
int totalNodes = N;
for (int i = 0; i < L; ++i) {
int k; cin >> k;
lineStops[i].resize(k);
for (int j = 0; j < k; ++j) cin >> lineStops[i][j];
posNodeId[i].resize(k);
for (int j = 0; j < k; ++j) {
posNodeId[i][j] = totalNodes++;
stationOccur[lineStops[i][j]].push_back({i, j});
}
}
// 建图（0-1 边）
struct Edge { int to, w; };
vector<vector<Edge>> g(totalNodes);
auto add_edge = [&](int u, int v, int w) {
g[u].push_back({v, w});
};
// 1) 线路位置 -> 对应站点（下车，费用 0）；2) 同一线路内前进（费用 0）
for (int i = 0; i < L; ++i) {
int k = (int)lineStops[i].size();
for (int j = 0; j < k; ++j) {
int station = lineStops[i][j];
int p = posNodeId[i][j];
add_edge(p, station - 1, 0); // P_{i,j} -> S_station
if (j + 1 < k) {
add_edge(p, posNodeId[i][j + 1], 0); // P_{i,j} -> P_{i,j+1}
}
}
}
// 3) 站点 -> 所有经过此站的线路位置（登车，费用 1）
for (int u = 1; u <= N; ++u) {
int su = u - 1; // S_u 节点编号
for (auto [li, idx] : stationOccur[u]) {
add_edge(su, posNodeId[li][idx], 1);
}
}
// 0-1 BFS 从 S_1 到 S_N
const int INF = 1e9;
vector<int> dist(totalNodes, INF);
deque<int> dq;
dist[0] = 0; // S_1 的编号为 0
dq.push_front(0);
while (!dq.empty()) {
int u = dq.front(); dq.pop_front();
for (auto e : g[u]) {
if (dist[e.to] > dist[u] + e.w) {
dist[e.to] = dist[u] + e.w;
if (e.w == 0) dq.push_front(e.to); else dq.push_back(e.to);
}
}
}
int ans = dist[N - 1]; // S_N 的编号为 N-1
if (ans >= INF) cout << "NO" << '\n';
else cout << max(0, ans - 1) << '\n';
return 0;
}
import java.util.*;
public class Main {
static class Edge { int to, w; Edge(int t, int w){ this.to=t; this.w=w; } }
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int L = sc.nextInt();
int N = sc.nextInt();
List<List<Integer>> lineStops = new ArrayList<>();
List<List<Integer>> posNodeId = new ArrayList<>();
for (int i = 0; i < L; i++) { lineStops.add(new ArrayList<>()); posNodeId.add(new ArrayList<>()); }
List<List<int[]>> stationOccur = new ArrayList<>();
for (int u = 0; u <= N; u++) stationOccur.add(new ArrayList<>());
int totalNodes = N; // 0..N-1 为站点节点
for (int i = 0; i < L; i++) {
int k = sc.nextInt();
lineStops.get(i).ensureCapacity(k);
for (int j = 0; j < k; j++) {
int s = sc.nextInt();
lineStops.get(i).add(s);
}
posNodeId.get(i).ensureCapacity(lineStops.get(i).size());
for (int j = 0; j < lineStops.get(i).size(); j++) {
posNodeId.get(i).add(totalNodes++);
int s = lineStops.get(i).get(j);
stationOccur.get(s).add(new int[]{i, j});
}
}
ArrayList<ArrayList<Edge>> g = new ArrayList<>();
for (int i = 0; i < totalNodes; i++) g.add(new ArrayList<>());
// 加边：位置->站点 (0)；位置->下一个位置 (0)
for (int i = 0; i < L; i++) {
List<Integer> ls = lineStops.get(i);
List<Integer> pid = posNodeId.get(i);
for (int j = 0; j < ls.size(); j++) {
int station = ls.get(j);
int p = pid.get(j);
g.get(p).add(new Edge(station - 1, 0));
if (j + 1 < ls.size()) g.get(p).add(new Edge(pid.get(j + 1), 0));
}
}
// 加边：站点->位置 (1)
for (int u = 1; u <= N; u++) {
int su = u - 1;
for (int[] occ : stationOccur.get(u)) {
int li = occ[0], idx = occ[1];
g.get(su).add(new Edge(posNodeId.get(li).get(idx), 1));
}
}
int INF = (int)1e9;
int[] dist = new int[totalNodes];
Arrays.fill(dist, INF);
Deque<Integer> dq = new ArrayDeque<>();
dist[0] = 0; dq.addFirst(0);
while (!dq.isEmpty()) {
int u = dq.pollFirst();
for (Edge e : g.get(u)) {
if (dist[e.to] > dist[u] + e.w) {
dist[e.to] = dist[u] + e.w;
if (e.w == 0) dq.addFirst(e.to); else dq.addLast(e.to);
}
}
}
int ans = dist[N - 1];
System.out.println(ans >= INF ? "NO" : Math.max(0, ans - 1));
}
}
from collections import deque
L, N = map(int, input().split())
line_stops = [] # 每条线路的站点序列
pos_node_id = [] # 每条线路每个位置对应的节点编号
station_occur = [[] for _ in range(N + 1)] # 站点 -> (线路, 位置)
total_nodes = N # 0..N-1 为站点节点 S_1..S_N
for i in range(L):
k = int(input())
stops = list(map(int, input().split()))
line_stops.append(stops)
ids = []
for j, s in enumerate(stops):
ids.append(total_nodes)
total_nodes += 1
station_occur[s].append((i, j))
pos_node_id.append(ids)
g = [[] for _ in range(total_nodes)] # (to, w)
def add_edge(u: int, v: int, w: int):
g[u].append((v, w))
# 位置 -> 站点 (0)；位置 -> 下一个位置 (0)
for i in range(L):
stops = line_stops[i]
ids = pos_node_id[i]
for j, s in enumerate(stops):
p = ids[j]
add_edge(p, s - 1, 0)
if j + 1 < len(stops):
add_edge(p, ids[j + 1], 0)
# 站点 -> 位置 (1)
for u in range(1, N + 1):
su = u - 1
for li, idx in station_occur[u]:
add_edge(su, pos_node_id[li][idx], 1)
# 0-1 BFS from S_1 (0) to S_N (N-1)
INF = 10 ** 9
dist = [INF] * total_nodes
dq = deque([0])
dist[0] = 0
while dq:
u = dq.popleft()
for v, w in g[u]:
if dist[v] > dist[u] + w:
dist[v] = dist[u] + w
if w == 0:
dq.appendleft(v)
else:
dq.append(v)
ans = dist[N - 1]
print("NO" if ans >= INF else max(0, ans - 1))
算法及复杂度
- 算法：二分图扩张（站点节点与线路位置节点）+ 0-1 BFS，登车记费
- 时间复杂度：
- 空间复杂度：
京公网安备 11010502036488号