CSP-S 2026 B题 地铁 题解（8个解法）
作者: | 更新日期:
地铁站与线路建模成图，利用线路数不超过 500 的性质，在线路图上预处理换乘最短时间，再枚举线路回答询问。
本文首发于公众号：天空的代码世界，微信号：tiankonguse
零、背景
之前已经分享了历年 CSP-J/S 的比赛题解与 《CSP-J 2026 的题解》。
这几天开始分享 CSP-S 2026 比赛题解。
为了避免四道题放在一篇导致文章过长，我计划每道题单独写一篇，最后再给出一个总结。
上篇文章分享了《CSP-S 2026 A题 能量水晶（6个解法）》
这篇文章分享 CSP-S 2026 第二道题「地铁 subway」的题解。
PS：pdf 题目和源码已经上传网盘，后台回复 CSP-S-2026 获取题目与源码。
一、题目
题意：B 市有 m 个地铁站，编号为 1 到 m。
每个地铁站都有一个站厅，地铁口与站厅之间有一条通道，往返耗时相同。
从第 v 个地铁站的地铁口走到站厅需要 w_v 的时间。
B 市有 n 条地铁线路，第 i 条线路依次经过 k_i 个地铁站。
在第 i 条线路的第 j 个站点处，从站厅走到该线路的站台需要 t_{i,j} 的时间，往返耗时相同。
同一条线路不会重复经过同一个地铁站。
每个地铁站最多有 d 条线路经过，且任意两个地铁站都可以通过若干条线路互相到达。
小 R 有 q 个出行计划，第 r 个计划从第 x 个站的地铁口出发，到第 y 个站的地铁口，且 x ≠ y。
途中可以进行若干次站内换乘，每次换乘都需要从一条线路的站台先走到站厅，再从站厅走到另一条线路的站台。
问每个出行计划的最小总步行时间，总步行时间为进出站与换乘的步行时间之和。
二、算法分析
先想清楚一个最基础的问题：一个出行计划的步行时间由哪几部分组成。
假设最终方案中，在起点 x 乘坐线路 A，在终点 y 乘坐线路 B。
步行时间分为三部分。
第一部分是进出站：从 x 的地铁口走到站厅需要 w_x，从 y 的站厅走到地铁口需要 w_y，这是固定成本。
第二部分是上下车：在 x 从站厅走到线路 A 的站台需要 t_{x,A}，在 y 从线路 B 的站台走回站厅需要 t_{y,B}。
第三部分是换乘：从线路 A 的站台走到站厅，再从站厅走到线路 B 的站台。
若线路 i 与线路 j 都在站点 v 经过，则它们可以在 v 处换乘，换乘步行时间为 t_{i,v} + t_{j,v}。
所以答案等于 w_x + w_y 加上「起点选一条线路、终点选一条线路」的最小换乘成本。
三、解法一：线路+站点构图，Floyd 全源最短路（40 分）
思路：线路和地铁站都当作一个点，构图，求全源最短路。
思考1：如何把「换乘」变成图上的边。
换乘的物理过程，就是从线路 A 的站台走到站厅，再从站厅走到线路 B 的站台。
如果把「线路」和「地铁站」都当作节点，线路节点 i 与它经过的站点节点 v 之间连一条无向边，边权为站厅与站台之间的步行时间。
这样「任意两条线路之间的最小换乘时间」就是线路节点之间的最短路。
思考2：全源最短路怎么求。
Floyd 算法可以直接求任意两个节点之间的最短路。 。
复杂度 O(V^3)。
思考3：如何回答询问。
任意两个站台之间的最短路 Floyd 已经求出来了，存在 dist(x, y) 中。
所以答案 = w_x + w_y + dist(x, y)。
复杂度： O((n + m)^3) 。
得分：40 分 。
核心代码如下：
void BuildEdge() { //
// 线路节点编号: (0, m)，站点节点编号: [m, n+m)
AdjacencyMatrix.resize(n + m, vector<ll>(n + m, INFL));
for (int lineId = 0; lineId < n; lineId++) {
int u = m + lineId;
for (auto [stationId, lineStationCost] : subway[lineId]) {
int v = stationId;
AdjacencyMatrix[u][v] = AdjacencyMatrix[v][u] = lineStationCost;
}
}
Floyd(AdjacencyMatrix); // 求所有节点之间的最小步行时间
}
void BuildQuery() {
for (auto [x, y] : querys) {
ll baseCost = W[x] + W[y] + AdjacencyMatrix[x][y];
printf("%lld\n", baseCost);
}
}
四、解法二：性质 A 构图 + Floyd（44 分）
性质 A 是每条线路至多经过 2 个地铁站。
若一条线路只有 1 个站点，它只能从该站出发又回到该站，而所有询问都满足 x ≠ y，所以这条线路永远不会被乘坐，直接丢弃。
若一条线路经过 u、v 两个站点，坐这条线路从 u 到 v 的步行时间为上车站台 + 下车站台时间。
所以线路可以变成站点 u 与 v 之间连边，边权为 t_{i,u} + t_{i,v}。
图只有 m 个站点节点，直接对站点邻接矩阵跑 Floyd。
复杂度： O(m^3)。
得分：44 分。
核心代码如下：
void SolverA() {
// 性质A：每条线路至多 2 个站点
// 单站点线路永远不会使用，直接丢弃
// 基于站点构造邻接矩阵
AdjacencyMatrix.resize(m, vector<ll>(m, INFL));
for (auto& line : subway) {
if (line.size() == 1) continue;
auto [u, uCost] = line[0];
auto [v, vCost] = line[1];
ll cost = min(vCost + uCost, AdjacencyMatrix[u][v]);
AdjacencyMatrix[u][v] = AdjacencyMatrix[v][u] = cost;
}
Floyd(AdjacencyMatrix); // 求所有站点之间的最小步行时间
BuildQuery();
}
五、解法三：邻接表 + m 次 Dijkstra（48 分）
思路：Floyd 计算全源最短路复杂度有点高，所以可以尝试构图邻接表，求 m 次 Dijkstra 最短路。
思考1：图如何存储。
基本思路：图还是解法一的 n + m 个节点，但不用邻接矩阵，需要用邻接表。
思考2：为什么从 Floyd 换成 Dijkstra。
Floyd 一次算完所有点对，但代价是 O(V^3)。
如果只从一个源点出发求到所有点的最短路，堆优化 Dijkstra 只需要 O(E log V)。
对于稀疏矩阵，跑 m 次 Dijkstra 更优。
复杂度：O(m · E · log V)。
得分：48 分。
核心代码如下：
void Dijkstra(int s, int n, vector<vector<pair<ll, ll>>>& S, vector<ll>& dist) {
dist[s] = 0;
priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, greater<pair<ll, ll>>> pque;
pque.push({0, s});
while (!pque.empty()) {
auto p = pque.top();
pque.pop();
ll v = p.second, d = p.first;
if (dist[v] < d) continue;
for (auto& [to, cost] : S[v]) {
if (dist[to] > dist[v] + cost) {
dist[to] = dist[v] + cost;
pque.push({dist[to], to});
}
}
}
}
void BuildEdge() { //
// 线路节点: [m, n+m)，站点节点: [0, m)
adjacencyTable.resize(n + m);
for (int lineId = 0; lineId < n; lineId++) {
int u = m + lineId;
for (auto [stationId, lineStationCost] : subway[lineId]) {
int v = stationId;
adjacencyTable[u].push_back({v, lineStationCost});
adjacencyTable[v].push_back({u, lineStationCost});
}
}
for (int stationId = 0; stationId < m; stationId++) {
Dijkstra(stationId, n + m, adjacencyTable, adjacencyMatrix[stationId]);
}
}
六、解法四：询问剪枝 + 多源 Dijkstra（48 分）
前面对全部 m 个站点都跑了 Dijkstra，但查询只关心询问中出现的站点。
用 hash 把每个查询的 x 与 y 并去重，只对这些站点跑 Dijkstra 即可。
得分：48分
核心代码如下：
unordered_set<int> queryStations; // 询问涉及的站点
// 读入查询时：
queryStations.insert(x);
queryStations.insert(y);
for (int stationId : queryStations) {
Dijkstra(stationId, n + m, adjacencyTable, adjacencyMatrix[stationId]);
}
七、解法五：性质 A 构图 + 多源 Dijkstra（48 分）
思路：Dijkstra 求最短路时也可以使用性质 A 构图，少 n 个点。
构图与上面类似，不过不使用邻接矩阵，而是使用邻接表，然后跑 Dijkstra 。
得分：48 分
核心代码如下：
void SolverA() {
adjacencyTable.resize(m);
for (auto& line : subway) {
if (line.size() == 1) continue;
auto [u, uCost] = line[0];
auto [v, vCost] = line[1];
adjacencyTable[u].push_back({v, vCost + uCost});
adjacencyTable[v].push_back({u, vCost + uCost});
}
for (int stationId : queryStations) {
Dijkstra(stationId, m, adjacencyTable, adjacencyMatrix[stationId]);
}
BuildQuery();
}
八、解法六：性质 B 构图 + BFS（48 分）
性质 B 保证所有 t 相同，于是图上所有边权相同。
边权全部相同时，Dijkstra 的优先队列退化为普通队列，直接 BFS 即可。
复杂度从 O(E log V) 降到 O(E)。
得分：48 分。
核心代码如下：
void Bfs(int s, int n, vector<vector<pair<ll, ll>>>& S, vector<ll>& dist) {
queue<ll> que;
que.push(s);
dist[s] = 0;
while (!que.empty()) {
ll u = que.front();
que.pop();
for (auto& [v, cost] : S[u]) {
if (dist[v] != INFL) continue;
que.push(v);
dist[v] = dist[u] + cost;
}
}
}
九、解法七：n ≤ 2 特判（56 分）
信息：第 20~21 组测试数据 n 不超过 2，线路极少，直接分情况讨论。
思考1：n = 1 时怎么办。
基本思路：只有一条线路，所有地铁站都在这一条线路上，全程无需换乘。
答案为 w_x + w_y + t_{x} + t_{y}，即起点上车与终点下车的步行时间。
hash 表预处理每个站到该线路站台的步行时间即可。
思考2：n = 2 时怎么办。
基本思路：最多换乘一次，即从 1 条线换到另 1 条线。
换乘只能发生在两条线路共同经过的站点 v。
两个线路可能有多个共同站点，需要取最小换乘时间。
查询 (x, y) 时，枚举 x 与 y 分别坐 1 号线与 2 号线的情况，组合共 4 中情况。
两条线路相同则不加换乘成本，不同则加最小换乘时间，取最小值。
小技巧：如果一个站点不在某条线路上，其到该线的最短路为无穷大。
得分：56分
核心代码如下：
void Solver_20_21() {
if (n == 1) {
for (auto [x, y] : querys) {
ll baseCost = W[x] + W[y] + stationCosts[x] + stationCosts[y];
printf("%lld\n", baseCost);
}
} else { // n = 2
for (auto [x, y] : querys) {
ll xx[2], yy[2];
for (int i = 0; i < 2; i++) {
xx[i] = Get(lines[i], x); // x 不在线路 i 上时为无穷大
yy[i] = Get(lines[i], y);
}
ll minCost = INFL;
for (int xi = 0; xi < 2; xi++) {
for (int yi = 0; yi < 2; yi++) {
ll cost = xx[xi] + yy[yi];
if (xi != yi) { // 换乘一次
cost += minSwap;
}
minCost = min(minCost, cost);
}
}
ll baseCost = W[x] + W[y] + minCost;
printf("%lld\n", baseCost);
}
}
}
十、解法八：线路图 + Floyd（100 分）
思考1：为何前面很难再提升分数。
前面做了很多优化，很难提升分数了。
这是因为构图一直以地铁站为点，构图都至少有 m 个点。
m 最大 5 × 10^5。
无论做全源最短路还是多次单源最短路，复杂度都至少是 O(m^2) 级别，必然超时。
再看数据范围，还有两个数字是突破口：
线路数 n ≤ 500，非常小。
经过每个地铁站的线路数 d ≤ 20，也很小。
这两个数据就是这道题正确解法的钥匙。
思考2：如何建立线路图。
换乘的本质，是从线路 i 的站台走到站厅，再从站厅走到线路 j 的站台。
两条线路 i、j 若能换乘，必须在某个站点 v 共同经过，换乘成本为 t_{i,v} + t_{j,v}。
把每条线路当作一个节点，对于每个地铁站 v，枚举经过它的所有线路对 (i, j)，在 i、j 之间连一条无向边，边权 t_{i,v} + t_{j,v}。
每个站点最多 d 条线路，枚举线路对 O(d^2)
总复杂度 O(m · d^2)。
思考3：线路图全源最短路怎么求。
线路图只有 n 个点，n ≤ 500。
Floyd 复杂度 O(n^3)。
思考4：如何回答询问。
对于询问的两个站点，每个站点最多有 d 条路线。
枚举两个站点的线路对，取最小换乘时间。
复杂度：O(q * d^2)。
总复杂度：O(m · d^2 + n^3 + q · d^2)。
得分：100分
核心代码如下：
void BuildEdge() { //
AdjacencyMatrix.resize(n, vector<ll>(n, INFL));
for (int i = 0; i < m; i++) {
int D = stations[i].size();
for (int j = 0; j < D; j++) {
auto [lineId1, lineOffset1] = stations[i][j];
ll lineCost1 = subway[lineId1][lineOffset1].second;
for (int k = j + 1; k < D; k++) {
auto [lineId2, lineOffset2] = stations[i][k];
ll lineCost2 = subway[lineId2][lineOffset2].second;
ll oldCost = min(AdjacencyMatrix[lineId1][lineId2], lineCost1 + lineCost2);
AdjacencyMatrix[lineId1][lineId2] = AdjacencyMatrix[lineId2][lineId1] = oldCost;
}
}
}
Floyd(AdjacencyMatrix); // 求所有线路之间的最小换乘时间
}
void BuildQuery() {
for (auto [x, y] : querys) {
ll ans = INFL;
ll baseCost = W[x] + W[y];
for (int stationX = 0; stationX < stations[x].size(); stationX++) {
auto [lineIdX, lineOffsetX] = stations[x][stationX];
ll lineCostX = subway[lineIdX][lineOffsetX].second;
for (int stationY = 0; stationY < stations[y].size(); stationY++) {
auto [lineIdY, lineOffsetY] = stations[y][stationY];
ll lineCostY = subway[lineIdY][lineOffsetY].second;
ans = min(ans, baseCost + lineCostX + lineCostY + AdjacencyMatrix[lineIdX][lineIdY]);
}
}
printf("%lld\n", ans);
}
}
十一、总结
CSP-S 的第二道题难度其实还好，但是数据量非常大，代码量也比较大，主要考察建图与最短路。
第一个思路是线路和地铁站都当点，Floyd 求全源最短路，得分 40。
性质 A 让构图时只使用地铁站，少了 n 个点，得分提升到 44。
Floyd 复杂度太高，改用邻接表 + m 次 Dijkstra，得分到 48。
询问剪枝、性质 A、性质 B 三个优化都能拿 48 分，但各有局限。
对 n ≤ 2 特判，得分到 56。
最后发现，只要构图围绕地铁站，图就至少有 m 个点，复杂度必然超时。
真正的突破口是线路数只有 500：把线路当节点建图，线路间最短路 O(n^3) 可以接受，回答询问只需要枚举起点与终点的线路。
《完》
-EOF-
本文公众号：天空的代码世界
个人微信号：tiankonguse
公众号 ID：tiankonguse-code
本文首发于公众号：天空的代码世界，微信号：tiankonguse
如果你想留言，可以在微信里面关注公众号进行留言。
