当前位置：首页>考研真题>真题解析:P17832 [CSP-S 2026] 地铁(图论建模·线路缩点·Floyd·换乘预处理)

真题解析:P17832 [CSP-S 2026] 地铁(图论建模·线路缩点·Floyd·换乘预处理)

2026-11-05 18:10:49

题目来源：洛谷 P17832 [CSP-S 2026] 地铁 / subway

题目大意

B 市有 m 个地铁站，编号 1 到 m；有 n 条地铁线路，编号 1 到 n。

第 v 个站有一个站厅，地铁口与站厅之间有一条通道，往返耗时相同，从地铁口走到站厅需要 w[v] 的时间。

第 i 条线路依次经过 k[i] 个站 a[i,1], a[i,2], …, a[i,k[i]]，同一条线路不会重复经过同一个站。在站 a[i,j] 处，从站厅走到第 i 条线路的站台需要 t[i,j] 的时间，往返耗时相同。

小 R 有 q 个出行计划。第 r 个计划从第 x 个站的地铁口出发，到第 y 个站的地铁口结束，途中可以任意次站内换乘：从一条线路的站台走回站厅，再从站厅走到另一条线路的站台。列车运行本身不计步行时间。求每个计划的最小总步行时间。

一次出行的步行时间由三部分组成：进站时从地铁口到站厅、每次换乘时站台与站厅之间的往返、出站时从站厅到地铁口。

数据范围：n ≤ 500，1 ≤ m ≤ Σk[i] ≤ 5×10⁵，1 ≤ d ≤ 20，1 ≤ q ≤ 10⁵，所有 w[v]、t[i,j] ≤ 10⁹。每个站最多被 d 条线路经过，线网保证连通，x ≠ y。

输入输出样例

第一行五个非负整数 c, n, m, d, q，依次是测试点编号、线路数、站数、每个站最多被几条线路经过、询问数；c = 0 表示这是样例。第二行 m 个数，是 w[1] 到 w[m]。接下来 n 行，每行 1 + 2k[i] 个数：先是 k[i]，然后是 k[i] 组 a[i,j], t[i,j]。最后 q 行，每行两个数 x, y。

样例 1 输入：

0 2 5 20 24 1 9 2 53 1 5 2 7 4 63 2 3 3 4 5 71 31 2

样例 1 输出：

5 个站，进站时间分别是 4、1、9、2、5。1 号线经过站 1、2、4，对应的 t 是 5、7、6；2 号线经过站 2、3、5，对应的 t 是 3、4、7。两条线在站 2 相交。

从站 1 到站 3：进站 w[1] = 4，走到 1 号线站台 t[1,1] = 5，坐到站 2 后在站内换到 2 号线，花 t[1,2] + t[2,1] = 7 + 3 = 10，坐到站 3 后走回站厅 t[2,2] = 4，出站 w[3] = 9，合计 4 + 5 + 10 + 4 + 9 = 32。

从站 1 到站 2：一路都在 1 号线上，4 + 5 + 7 + 1 = 17。

样例 2 输入：

0 3 7 20 28 3 6 1 7 2 93 1 4 2 5 5 1003 2 6 3 1 7 24 3 2 5 100 4 6 6 71 62 3

样例 2 输出：

考点梳理

一、建图先定"谁是点"。 这题最容易翻车的地方不是最短路算法，而是选错顶点。站有 5×10⁵ 个，线路只有 500 条。凡是跟"站数"同阶的做法（站点两两建表、对每个站跑最短路）在空间上就先死了；而线路数只有 500，500³ 的 Floyd 完全放得下。数据范围里两个变量的量级差了三个数量级，这个差值就是题目给的提示。

二、换乘的代价可以预先折算成"两条线之间的一条边"。 在站 s 从线路 i 换到线路 j，步行的只有"i 的站台到站厅"加"站厅到 j 的站台"，也就是 t[i,s] + t[j,s]。这个值只和 i、j 两条线以及它们共用的站有关，跟具体是哪一趟出行无关。把每条线路当成一个点，两条线之间的边权取它们所有共用站上 t[i,s] + t[j,s] 的最小值，换乘问题就变成了普通最短路。

三、Floyd 求线路之间的最短路。 顶点数 n ≤ 500，n³ = 1.25×10⁸，标准 Floyd 足够。求出来的 dis[i][j] 含义是"人已经站在线路 i 的站台上，走到线路 j 的站台，最少要步行多久"，其中 dis[i][i] = 0。

四、查询靠枚举而不是再跑最短路。 q 到 10⁵，每次现跑最短路必然超时。但一次出行的第一段一定是"从起点站上某条经过它的线"，最后一段一定是"从某条经过终点的线下车"，中间都是线网内部的最短路。而每个站最多被 d ≤ 20 条线经过，起点线路和终点线路的组合最多 20 × 20 = 400 组。把 dis 预处理出来，单个询问只要枚举这 400 组取最小。

五、64 位整型与读入量。 单次步行时间到 10⁹，一次出行要换乘若干次，累加能到 10¹² 量级，全程 long long。输入规模 Σk[i] + q ≤ 6×10⁵ 个数，用手写快读最稳。

解题思路

1. 为什么不能拿站点当点

最直觉的建模是：每个站一个点，每条线一个点，站和线之间连边，边权是 t，然后跑最短路。这个模型本身没错，样例也能过，但它把 5×10⁵ 个站拉进了图里。想预处理所有站对之间的答案，需要 m² 的表，2.5×10¹¹ 个 long long，光一个测试点就要 2TB。

真正决定这张图大小的不是站，是线。一次出行里人做的动作只有三种：在起点站上某条线、在某个站从一条线换到另一条线、在终点站从某条线下车。这些动作全部发生在"线"上，站只是提供换乘的地点。所以顶点应该选线路。

2. 换乘代价：两条线之间的边权

在站 s 从线路 i 换到线路 j，人要走的路线是：

i 的站台 --t[i,s]--> 站厅 --t[j,s]--> j 的站台

代价是 t[i,s] + t[j,s]。这里不出现 w[s]：w[s] 是"地铁口到站厅"的时间，换乘不出站，用不到它。

两条线可能共用多个站，取其中最小的那个作为边权：

dis[i][j] = min over s in (i ∩ j) of ( t[i,s] + t[j,s] )

线路自己到自己不需要换乘，所以 dis[i][i] = 0。

3. 用 Floyd 把边权推成最短路

n ≤ 500，直接三重循环。初始化 dis[i][i] = 0、其余为无穷大，把上一步算出的共用站边权填进去，跑完 Floyd 得到的 dis[i][j] 就是"站在线路 i 的站台上，走到线路 j 的站台"的最小步行时间，中间可以经过任意多条线路。

这一步是整道题的关键。只做"两条线直接换乘一次"是不够的：样例 2 里最短路要连续换两次线，中间那条线路必须被 Floyd 串进去。

4. 询问：起点线乘终点线

人从站 x 出发，第一步只能选一条经过 x 的线路 i，花 w[x] 进站、t[i,x] 上站台；最后一步只能从一条经过 y 的线路 j 下车，花 t[j,y] 回站厅、w[y] 出站。中间的部分就是 dis[i][j]。于是

ans = min over i in lines(x), j in lines(y) of      ( w[x] + t[i,x] + dis[i][j] + t[j,y] + w[y] )

其中 lines(x) 是经过站 x 的线路集合，大小不超过 d。w[x]、w[y] 和枚举无关，可以最后再加。

i = j 的情况也在式子里：dis[i][i] = 0，等价于"全程只坐一条线"，这就覆盖了不需要换乘的出行。

5. 手算样例 2，验证换乘要连着算

样例 2 里 w = [8, 3, 6, 1, 7, 2, 9]，三条线分别是：

线路	经过的站与对应的 t
1 号线	站 1：4，站 2：5，站 5：100
2 号线	站 2：6，站 3：1，站 7：2
3 号线	站 3：2，站 5：100，站 4：6，站 6：7

询问 1 到 6。经过站 1 的只有 1 号线，经过站 6 的只有 3 号线。1 号线和 3 号线共用站 5，直接换乘的代价是 100 + 100 = 200，几乎不可行；实际最优路线要在站 2 换 2 号线、在站 3 再换 3 号线：

dis[1][3] = (5 + 6) + (1 + 2) = 14

前一个括号是在站 2 换乘的代价，后一个括号是在站 3 换乘的代价。

答案 = 8 + 4 + 14 + 7 + 2 = 35，与样例一致。这一算就能看出：预处理出来的必须是"线路到线路"的最短路，而不是"两条线直接换一次"的代价。

询问 2 到 3 更简单：两个站都在 2 号线上，dis[2][2] = 0，答案 = 3 + 6 + 0 + 1 + 6 = 16。

6. 实现上的几处细节

一是站点到线路的存储。 读入时每条线给出的是"线路到站点"的顺序，但查询需要"站到经过它的线路"。Σk[i] 到 5×10⁵，用 vector 数组会有大量小对象，改成桶排序式的 CSR：先把所有（站，线，时间）三元组读进三个平行数组，统计每个站出现次数，做前缀和得到每个站在一维数组里的区间 [off[v], off[v+1])，再把三元组按站分桶填进 gLine 和 gTime。这样既省内存，查询时也是连续访问。

二是建边时不要重复枚举。 每个站内部对它经过的线路两两配对，c 条线有 c(c−1)/2 对。因为 c ≤ 20 且所有 c 之和就是 Σk[i] ≤ 5×10⁵，配对总数上界是 10Σk[i] ≈ 5×10⁶，可以接受。

三是无穷大的选取。 真实答案最大 10¹² 量级，把 INF 设成 10¹⁵ 就够用，并且 dik + dk[j] 最大 2×10¹⁵，不会溢出 long long。用 10¹⁸ 反而有溢出风险。

四是 dis[i][i] 必须初始化成 0。 漏了这一步，同一条线直达的询问会被算成绕一大圈。

五是读入。 数据量在百万级，手写 fread 快读比 cin 稳。

参考代码

#include <bits/stdc++.h>using namespace std;typedef long long ll;const int MAXN = 505;const int MAXM = 600005;const ll INF = (ll)1e15;static char ibuf[1 << 22];static int ipos = 0, ilen = 0;inline char gc(){    if (ipos == ilen) {        ilen = (int)fread(ibuf, 1, sizeof(ibuf), stdin);        ipos = 0;        if (ilen <= 0) return 0;    }    return ibuf[ipos++];}inline ll readInt(){    char ch = gc();    while (ch < '0' || ch > '9') {        if (!ch) return 0;        ch = gc();    }    ll x = 0;    while (ch >= '0' && ch <= '9') {        x = x * 10 + (ch - '0');        ch = gc();    }    return x;}int n, m, q, d;ll w[MAXM];int sid[MAXM], lid[MAXM];ll stm[MAXM];int cnt[MAXM], off[MAXM], cur[MAXM];int gLine[MAXM];ll gTime[MAXM];ll dis[MAXN * MAXN];int main(){    int c = (int)readInt();    n = (int)readInt();    m = (int)readInt();    d = (int)readInt();    q = (int)readInt();    for (int v = 1; v <= m; v++) w[v] = readInt();    int tot = 0;    for (int i = 1; i <= n; i++) {        int k = (int)readInt();        for (int j = 0; j < k; j++) {            sid[tot] = (int)readInt();            stm[tot] = readInt();            lid[tot] = i;            tot++;        }    }    for (int i = 0; i < tot; i++) cnt[sid[i]]++;    off[1] = 0;    for (int v = 2; v <= m + 1; v++) off[v] = off[v - 1] + cnt[v - 1];    for (int v = 1; v <= m + 1; v++) cur[v] = off[v];    for (int i = 0; i < tot; i++) {        int p = cur[sid[i]]++;        gLine[p] = lid[i];        gTime[p] = stm[i];    }    for (int i = 1; i <= n; i++) {        ll *row = dis + i * MAXN;        for (int j = 1; j <= n; j++) row[j] = INF;        row[i] = 0;    }    for (int v = 1; v <= m; v++) {        int L = off[v], R = off[v + 1];        for (int p = L; p < R; p++) {            int i = gLine[p];            ll ti = gTime[p];            for (int r = p + 1; r < R; r++) {                ll val = ti + gTime[r];                int j = gLine[r];                if (val < dis[i * MAXN + j]) dis[i * MAXN + j] = val;                if (val < dis[j * MAXN + i]) dis[j * MAXN + i] = val;            }        }    }    for (int k = 1; k <= n; k++) {        ll *dk = dis + k * MAXN;        for (int i = 1; i <= n; i++) {            ll dik = dis[i * MAXN + k];            if (dik >= INF) continue;            ll *di = dis + i * MAXN;            for (int j = 1; j <= n; j++) {                ll val = dik + dk[j];                if (val < di[j]) di[j] = val;            }        }    }    while (q--) {        int x = (int)readInt(), y = (int)readInt();        ll ans = INF;        int Lx = off[x], Rx = off[x + 1];        int Ly = off[y], Ry = off[y + 1];        for (int p = Lx; p < Rx; p++) {            int i = gLine[p];            ll ti = gTime[p];            ll *di = dis + i * MAXN;            for (int r = Ly; r < Ry; r++) {                ll val = ti + di[gLine[r]] + gTime[r];                if (val < ans) ans = val;            }        }        printf("%lld\n", ans + w[x] + w[y]);    }    return 0;}

变量与前面的推导一一对应：n 是线路数、m 是站数，w[v] 是进站时间，gLine 和 gTime 存的是"某个站经过的线路及其 t"，dis[i * MAXN + j] 就是 dis[i][j]，x、y 是询问的起终点，ans 里存的是 w[x] + t[i,x] + dis[i][j] + t[j,y] + w[y] 去掉两端进站出站时间之后的那部分。

复杂度分析

设 S = Σk[i]，第 s 个站被 c[s] 条线路经过。

• 读入与建桶：O(S + m)。
• 建线路之间的边：Σ c[s](c[s] − 1) / 2。因为 c[s] ≤ 20 且 Σ c[s] = S，上界是 10S，即 5×10⁶ 次。
• Floyd：O(n³)，n = 500 时 1.25×10⁸ 次。
• 询问：每个 O(c[x] · c[y]) ≤ d² = 400，总计 O(q · d²) = 4×10⁷。

总时间 O(S + n³ + q·d²)，空间 O(n² + m + S)。按最大数据实测，读入加计算约 0.2 秒，内存在 1GB 限制内绰绰有余。

真题解析:P17832 [CSP-S 2026] 地铁(图论建模·线路缩点·Floyd·换乘预处理)

题目大意

输入输出样例

考点梳理

解题思路

1. 为什么不能拿站点当点

2. 换乘代价：两条线之间的边权

3. 用 Floyd 把边权推成最短路

4. 询问：起点线乘终点线

5. 手算样例 2，验证换乘要连着算

6. 实现上的几处细节

参考代码

复杂度分析

推荐阅读

真题解析直播预告|GESP2026年9月认证Python三级

26秋七年级上册历史期中复习知识点总结记背 F2618