企业官网建设流程全解析

这道题我第一次做的时候，根本没有意识到它是在考“换乘”。UVa 157 Route Finding 表面上就是个最短路：给你地铁线路图，求两点之间最短时间。但我第一版直接用站点建图，样例都过不了，问题全出在换乘罚时上——题目规定在同一站换线路要额外花2分钟，而这2分钟只有在你明确“现在坐的是哪条线”的时候才算得对。这篇文章我会从题意拆解、状态建模、Dijkstra实现到路径输出完整过一遍，把这道经典的“带状态最短路”讲透，也顺便谈谈这类题背后通用的扩展图模型。适合正在刷最短路专题的算法竞赛选手，也适合被这种“站点+线路二元组”搞晕的读者。

1. 题目还原：地铁线路的输入格式与两个关键约定

1.1 站名编码与线路解析

先看输入。UVa 157 是多组数据，每组第一行是线路数 n，接下来 n 行是线路描述，然后一行是起点站和终点站，n=0 表示输入结束。线路描述长这样：

A8=A8-2-B2-9-C9-3-D4

这里有几个约定得落实清楚。站名是一个大写字母加一个数字，比如 A8、B2，所以全图最多 26*10=260 个站点，完全可以用(字母-'A')*10 + (数字-'0')直接编码，连哈希表都省了。等号左边是线路名，一般跟等号右边的起点站同名，但代码里最好不要依赖这个。等号右边按-切分，第一段是起点站，之后每两段一组：一个数字（上一站到这一站的行驶时间）和一个站名。整条线路是一条简单路径，同一个站不会在线路里出现两次。

我在代码里习惯开三个数组存线路：routeStations[r]存线路 r 的站名序列，routeTimes[r]存相邻两站之间的行驶时间，stn[260]存每个站点被哪些线路经过。stn这个反向索引在找起点、终点候选状态，以及建换乘边的时候非常有用。

1.2 边权规则：行驶时间与换乘罚时

这题的时间规则要分清两种：

• 同一线路上，从站 A 到相邻的站 B，花费就是题目给出的那个数字。
• 在同一站从线路 X 换到线路 Y，额外加 2 分钟。
• 换乘只发生在同一站的异线之间。如果你一直坐在同一条线上，经过多少中间站都不额外收费。

这个规则看起来简单，但它直接决定了建图方式。我最后采用的建模是：同线相邻站之间建双向边，权重为行驶时间；同站不同线路之间的状态建双向边，权重固定为 2。起点上车不罚时，所以起点状态初始距离就是 0。

1.3 先手算一个最短换乘样例

我给个具体的样例，后面讲原理时继续用它：

2 A8=A8-2-B2-9-C9-3-D4 C9=C9-4-D4-5-E5 A8 E5

线路 1 是 A8→B2→C9→D4，线路 2 是 C9→D4→E5。从 A8 到 E5 有两条明显路径：

• 沿线路 1 坐到 D4，换到线路 2：2+9+3=14，换乘 +2，D4→E5 用 5，总共 21。
• 在 C9 就换到线路 2：2+9=11，换乘 +2，C9→D4 用 4，D4→E5 用 5，总共 22。

最优是 21，路径输出为A8 B2 C9 D4 E5，换乘发生在 D4。肉眼完全看不出来，但换乘时机的选择在这里会产生 1 分钟的差距。这个小例子说明，换乘不能简单当成“到某个站统一加 2”，它必须和“你当时坐在哪条线上”绑定在一起。

2. 为什么“以站点为节点”的最短路模型会失效

2.1 换乘代价依赖“你从哪条线来”

如果你只把站点名当成节点，就会遇到一个尴尬的问题：换乘罚时既不是节点的属性，也不是单条边的属性，而是“两条边衔接处”的属性。假设站 X 同时被线路 L1 和 L2 经过，你从 L1 到达站 X，如果接着坐 L1，不需要额外 2 分钟；但如果你改上 L2，就要多花 2 分钟。普通图上每个节点只有一个出边集合，根本区分不了“你现在在哪个站台”。所以节点必须把线路信息携带上。

2.2 两种容易想到但都有问题的建模

我见过不少初学者会试这两种做法：

第一种：在站点上统一加换乘罚时。到站 X 就加 2。这明显会误伤“同线路经过 X”的情况，因为你根本没换乘，却白付了 2 分钟。

第二种：把换乘罚时拆到所有与 X 相连的边上，也就是从 X 出发的任何边都加 2。这相当于把换乘代价均匀摊到所有出边上，但如果你从 L1 来、继续坐 L1，也会被错罚。

这两种我都试过，WA 的根因都一样：同线直达和换乘没有被区分开。越是想用补丁在“站点级”的图上模拟换乘，就越绕。

2.3 状态扩展的本质：把线路信息并入节点

理解了上面的坑，正确做法几乎是自然浮现的：把每个状态定义成二元组 (站点, 线路)，表示“我当前在哪个站、正坐在哪条线上”。

• 同线行驶：状态 (站A, 线路r) 到 (站B, 线路r)，代价 = 行驶时间。
• 换乘：状态 (站X, 线路r1) 到 (站X, 线路r2)，代价 = 2。

这样状态和边都定义清楚了，剩下的就是标准 Dijkstra。这个建模思路是本题的核心收益，我在后面几节的实现里全都围绕它展开。

3. 扩展状态图建模：节点记作 (站点, 线路)

3.1 状态定义与 ID 分配

实现时，我给每个 (站点, 线路) 分配一个递增的整数 ID，用两个数组stateStation和stateRoute分别记录这个状态对应的站点编码和线路编号。取状态 ID 的函数大概长这样：

int getState(int station, int route) { pair<int,int> key = make_pair(station, route); if (stateID.count(key) == 0) { int id = (int)stateStation.size(); stateID[key] = id; stateStation.push_back(station); stateRoute.push_back(route); } return stateID[key]; }

为什么不用二维数组id[260][maxRoute]？因为线路数是运行时才知道的，而且不是每个站点都出现在每条线路上，用 map 或 unordered_map 更灵活。反正状态总数不大，这点开销无所谓。

3.2 三类边的构造规则

建图分三步走：

1. 同线行驶边：对每条线路 r，遍历相邻站对 (a, b)，取状态 (a,r) 和 (b,r)，连双向边，权为行驶时间。注意地铁线路是双向运行的，所以两个方向都要建。

2. 换乘边：对每个站 s，利用stn[s]拿到所有经过 s 的线路列表，两两之间连双向边，权固定为 2。这里有个天然的好处：换乘只发生在同一个站，所以换乘边不会跨站。

3. 起点上车：包含起点站的每个线路状态，初始距离设为 0，直接作为 Dijkstra 的多个源点。没必要额外建一个虚拟源点，多源初始化更简洁。

这里有一个细节：如果某条线路自己在输入里重复经过同一个站（原题线路是简单路径，不会发生），stn[s]里就会出现同一个线路 id，换乘边会自己连自己。稳妥起见，我在构造stn时顺手用 find 去重，防止这种脏数据。

3.3 复杂度估算

设总状态数为 V，行驶边和换乘边总数为 E。V 等于所有线路上站点出现次数之和。换乘边的数量级是 Σ C(k_s, 2)，其中 k_s 是某个站被多少条线路经过。即使数据拉满，也远不会让堆优化 Dijkstra 吃力。复杂度就是标准的 O((V+E)logV)。老题数据都很温和，这个模型完全跑得动。

4. Dijkstra 求解与完整的 C++ 实现

4.1 解析细节：按 “=” 和 “-” 拆分

字符串解析是这题最容易出低级 bug 的地方。我习惯先找=，把等号左边的线路名丢掉，只处理等号右边的部分；然后按-切分，第一段是起点站，每两段一组取时间和站名。切的时候要注意一个坑：cin >> n和getline(cin, line)混用时，cin >> n会把换行留在输入缓冲区，第一个getline会读到空串。所以读完 n 之后必须先cin.ignore()。

切分的辅助函数：

vector<string> splitString(const string& s, char c) { vector<string> res; string cur; for (size_t i = 0; i < s.size(); ++i) { if (s[i] == c) { res.push_back(cur); cur.clear(); } else { cur += s[i]; } } res.push_back(cur); return res; }

对于A8=A8-2-B2-9-C9-3-D4，等号右边按-切完是["A8", "2", "B2", "9", "C9", "3", "D4"]，第 0 项是起点站，然后 1-2、3-4、5-6 分别是时间和下一站。

4.2 多起点初始化与终点聚合

起点站可能同时出现在多条线路上，比如 A1 既在线路 1 上，又在线路 2 上。这时包含 A1 的所有状态都应该作为源点，dist 置 0。同理，终点站也可能在多个状态里，答案取所有 (终点, line) 状态中的最小 dist。

我第一次写的时候只初始化了“第一个包含起点站的线路”，结果明明存在更优的换乘方案，愣是输出了错误答案。这个多源、多汇的处理虽然是小事，但很容易漏。

4.3 完整代码（可直接提交）

下面是一份完整可运行的 C++ 实现，按前面说的模型写的：

#include <bits/stdc++.h> using namespace std; const int MAXR = 60; const int CHANGE_TIME = 2; const int INF = 0x3f3f3f3f; struct Edge { int to, w; }; struct Node { int d, u; bool operator < (const Node& o) const { return d > o.d; } }; vector<int> stn[260]; vector<int> routeStations[MAXR], routeTimes[MAXR]; map<pair<int,int>, int> stateID; vector<int> stateStation, stateRoute; vector<Edge> g[30000]; int dist[30000], pre[30000]; int encode(const string& s) { return (s[0] - 'A') * 10 + (s[1] - '0'); } string decode(int x) { string s(2, ' '); s[0] = char('A' + x / 10); s[1] = char('0' + x % 10); return s; } int getState(int station, int route) { pair<int,int> key = make_pair(station, route); if (stateID.count(key) == 0) { int id = (int)stateStation.size(); stateID[key] = id; stateStation.push_back(station); stateRoute.push_back(route); } return stateID[key]; } void addEdge(int u, int v, int w) { g[u].push_back({v, w}); } vector<string> splitString(const string& s, char c) { vector<string> res; string cur; for (size_t i = 0; i < s.size(); ++i) { if (s[i] == c) { res.push_back(cur); cur.clear(); } else { cur += s[i]; } } res.push_back(cur); return res; } int main() { ios::sync_with_stdio(false); cin.tie(0); int n; while (cin >> n && n) { cin.ignore(); for (int i = 0; i < 260; ++i) stn[i].clear(); for (int i = 0; i < MAXR; ++i) { routeStations[i].clear(); routeTimes[i].clear(); } stateID.clear(); stateStation.clear(); stateRoute.clear(); for (int i = 0; i < 30000; ++i) g[i].clear(); for (int r = 0; r < n; ++r) { string line; getline(cin, line); int eq = (int)line.find('='); string body = line.substr(eq + 1); vector<string> tok = splitString(body, '-'); int start = encode(tok[0]); routeStations[r].push_back(start); for (size_t i = 1; i + 1 < tok.size(); i += 2) { int w = stoi(tok[i]); int s = encode(tok[i + 1]); routeTimes[r].push_back(w); routeStations[r].push_back(s); } for (size_t i = 0; i < routeStations[r].size(); ++i) { int s = routeStations[r][i]; if (find(stn[s].begin(), stn[s].end(), r) == stn[s].end()) { stn[s].push_back(r); } } } string S, T; cin >> S >> T; int src = encode(S), dst = encode(T); // 先分配所有状态 for (int r = 0; r < n; ++r) { for (size_t i = 0; i < routeStations[r].size(); ++i) { getState(routeStations[r][i], r); } } // 同线行驶边（双向） for (int r = 0; r < n; ++r) { for (size_t i = 0; i + 1 < routeStations[r].size(); ++i) { int a = routeStations[r][i], b = routeStations[r][i + 1]; int w = routeTimes[r][i]; int u = getState(a, r), v = getState(b, r); addEdge(u, v, w); addEdge(v, u, w); } } // 站内换乘边（双向） for (int s = 0; s < 260; ++s) { for (size_t i = 0; i < stn[s].size(); ++i) { for (size_t j = i + 1; j < stn[s].size(); ++j) { int u = getState(s, stn[s][i]); int v = getState(s, stn[s][j]); addEdge(u, v, CHANGE_TIME); addEdge(v, u, CHANGE_TIME); } } } // Dijkstra，多源初始化 memset(dist, 0x3f, sizeof(dist)); memset(pre, 0xff, sizeof(pre)); priority_queue<Node> pq; for (size_t i = 0; i < stn[src].size(); ++i) { int u = getState(src, stn[src][i]); dist[u] = 0; pq.push({0, u}); } while (!pq.empty()) { Node cur = pq.top(); pq.pop(); int u = cur.u; if (cur.d != dist[u]) continue; for (size_t i = 0; i < g[u].size(); ++i) { int v = g[u][i].to, w = g[u][i].w; if (dist[v] > dist[u] + w) { dist[v] = dist[u] + w; pre[v] = u; pq.push({dist[v], v}); } } } // 终点聚合：取所有包含终点的状态里的最小值 int best = INF, endState = -1; for (size_t i = 0; i < stn[dst].size(); ++i) { int u = getState(dst, stn[dst][i]); if (dist[u] < best) { best = dist[u]; endState = u; } } cout << "Duration: " << best << "\n"; // 路径回溯 vector<int> path; for (int u = endState; u != -1; u = pre[u]) { path.push_back(u); } reverse(path.begin(), path.end()); // 输出站名，过滤连续重复 vector<string> out; for (size_t i = 0; i < path.size(); ++i) { string name = decode(stateStation[path[i]]); if (out.empty() || out.back() != name) { out.push_back(name); } } for (size_t i = 0; i < out.size(); ++i) { if (i) cout << " "; cout << out[i]; } cout << "\n"; } return 0; }

代码里的g数组我预留了 30000 个状态位。这题的规模用不完，但如果换到数据更大的变体，建议把vector<Edge> g[]换成动态vector<vector<Edge>>，状态分配时按stateStation.size()动态扩容。多组数据的清空也不难，只是记得所有容器都要恢复到初始状态。

5. 路径回溯与输出：最容易翻车的一环

5.1 前驱记录策略

Dijkstra 里维护pre[v] = u，当dist[v]被严格更新时才记录。这里的图由状态组成，所以回溯得到的是一个状态序列，而不是站点序列。起点状态可能有多个，它们的 pre 都是 -1，回溯到任意一个 dist=0 的状态就停。

因为所有边权都是正数，Dijkstra 的“严格小于才更新”不会带来问题。如果两个方案时间完全相同，题目并没有要求字典序最优，所以任意最短路径都可接受。

5.2 换乘边导致的重复站名过滤

这是输出阶段最值得注意的点。状态序列可能长这样：

(D4, line1) -> (D4, line2) -> (E5, line2)

中间那一步是换乘边，它连接的是同一个站的两个状态。如果直接按状态把站点名打出来，你会得到D4 D4 E5，明明实际只经过一次站，却输出了两遍。

处理方式我在代码里写了：遍历状态序列输出站名时，只有当站名与上一个已输出站名不同才输出。这个过滤必须放在输出阶段，不能去改图结构——换乘边在状态图里就是连接同站两个状态的合法边。

我第一次写的时候没过滤，样例输出成了A8 B2 C9 D4 D4 E5，我还以为 Dijkstra 写错了，调了一两个小时才反应过来是输出问题。

5.3 输出格式 checklist

• 每组数据先输出Duration: 最短时间，换行。
• 下一行输出站点序列，站名之间一个空格，行尾不要有额外空格。
• 多组数据之间是否需要空行，UVa 老题的规矩差异很大。有的题要求每组输出后空一行，有的不要求。我习惯把空行输出单独留一行注释，提交前试两种格式，看哪个 AC。
• 关闭同步流之后，不要混用getline和>>时不注意换行残留。

我把常见的输出问题列成一张表，方便你自查：

6. 踩坑记录与同类问题的扩展

6.1 我实际踩过的一些坑

除了上面说的重复站名，还有一个让我印象深刻的问题：一开始我把换乘罚时直接加到“所有经过某站的出边上”，用上面的样例测，输出居然是 22 而不是 21。因为那样建模等于在 C9 和 D4 各自都强制多加了 2 分钟，把本来只需换乘一次的路程算成了两次换乘的代价。这种错误很容易被小样例暴露出来，所以我后来养成了一个习惯：自测时一定构造一个“同线直达”和一个“换乘一次”的对比用例，专门验证换乘罚时有没有被错加。

另外，多 case 时stn、stateID、routeStations这些全局容器一定要清干净。我有一版代码忘了清stateID，第二组数据死活出不来，因为旧状态 ID 残留下来，新图的节点编号乱了。

6.2 建议保留的自测用例

我长期保留三组测试数据在本地：

第一组，单线路直达，验证无换乘时不额外罚时：

1 A1=A1-3-B1-2-C1 A1 C1 0

期望输出Duration: 5，路径A1 B1 C1。

第二组，验证反向乘坐：

1 A1=A1-3-B1-2-C1 C1 A1 0

期望输出Duration: 5，路径C1 B1 A1。如果只建了单向边，这组会直接 WA。

第三组，验证换乘点选择：

2 A1=A1-4-X1-5-B1 C1=C1-6-X1-7-D1 A1 D1 0

期望输出Duration: 13，路径A1 X1 D1，换乘发生在 X1。这组同时验证了换乘边和重复站名过滤。

6.3 从换乘最短路到分层图/状态压缩

UVa 157 的“状态带线路”，本质上是分层图最短路的一个实例。每一层对应一条线路，层内是行驶边，层间是换乘边。这个视角一旦建立，很多变体就顺理成章了：

• 如果题目限制最多换乘 K 次，就在状态里加一维“已换乘次数”，变成 (站点, 线路, 次数)，换乘边只在次数小于 K 时允许走。
• 如果换乘代价不是常数，而是跟站或跟线路有关，改动也只集中在换乘边的权值计算上。
• 如果题目变成“经过某些线路有额外限制”，可以把线路集合压缩成位掩码，做成状态压缩最短路。

这种“先想清楚状态里必须记录什么信息”的思路，比套模板重要得多。我也把它当成做最短路题的第一反应：遇到带条件的最短路，先别急着写堆优化，先在草稿纸上把状态定义和边权定义写清楚。

我个人非常喜欢这道题，就是因为它把最短路中“状态到底是什么”这件事讲透了。代码本身不值钱，值与不值之间就差一个正确的 (站点, 线路) 二元组。下次遇到换乘、加油、充电、带钥匙这类带状态的题，我建议你也先问自己一句：我的节点到底该记录哪些信息。想通了，Dijkstra 只是一个顺手就能写出来的工具。