企业官网建设流程全解析

1. 先把"怎么走"翻译成图论问题

“人民广场怎么走？”这种问题，日常交给手机地图就够了。但我自己作为一个写代码的人，更喜欢把它当成一个算法题来拆：给定一张城市地铁网、一个起点站、一个终点站，程序要自己算出该怎么坐、在哪换、换几次。回答这个问题的底层核心，就是地铁换乘算法。

这篇文章聊的不是某个商业App的完整方案，而是一个用C语言就能实现的迷你换乘引擎。我会完整走一遍从图建模、数据结构选型、Dijkstra变体设计，到代码实作的全过程，同时把"换乘次数""换乘时间"这类现实约束翻译成算法里的权重。文章最后会给出可以直接编译运行的完整C代码，以及几组真实查询的运行结果。

适合两类人看：一类是刚学完数据结构、想看看最短路径算法怎么落地的新手；另一类是想在项目里快速做一个轻量级出行路线模块、又不想引入重量级依赖的开发者。看完至少能自己扩展出带首末班时间、带站点实时客流等功能的换乘原型。

1.1 站点是点、区间是边：一张地铁网的图模型

要把"人民广场怎么走"交给程序，第一步就是把地铁网变成程序认识的东西。最自然的建模方式，是把地铁网抽象成一张无向图。

站点是顶点，相邻两站之间的轨道区间是边。每条边至少携带三个信息：两端站点、属于哪条线路、跑完这个区间要多久。换乘站呢？就是一个同时被多条线路共用的顶点。打个比方，把地铁图想成一张"只能沿着轨道走的旅游地图"，你从大学城走去火车站，唯一能走的路就是图上画出来的轨道区间；走到交叉口（换乘站）时，你可以从一条轨道换到另一条轨道，前提是付出一点额外体力——在真实世界里就是下车、走路、等车。

这个抽象的价值在于，它把"人民广场怎么走"从一个日常问路问题，变成了一个数学问题：在带权无向图中，找一条从起点站到终点站的代价最小路径。一旦完成这个翻译，后面所有算法都有章可循。

无向图的选择也有讲究。绝大多数地铁线路是双向运行的，所以每添加一个区间，都要同时建立两个方向的边。如果漏掉反方向，算法就会跑出"坐过站之后回不去"这种反人类结果。环线也不特殊，它只是两条边首尾相接形成闭合，建模方式没有任何额外负担。

1.2 为什么不能暴力枚举所有路线

很多刚接触这个问题的人，第一反应是：把从起点到终点的所有路径都枚举一遍，挑一条最短的不就行了吗？

理论上没错，但只对极小规模成立。假设网络有30条线路、500个站点，路径数量会随着途经站数指数级增长。即使能暴力算完，响应时间也完全不可控；更何况出行App同一时刻要响应几十万个查询。暴力的另一个问题是，人的出行需求里其实藏着"最少换乘"这个隐性指标，纯距离最短往往不是人想要的。比如大学城到机场，看起来近但需要换三次线，多数人宁愿多坐两站，在大站换一次。这种约束虽然也能加进穷举，但会让搜索空间膨胀得更厉害。

所以工程上通常把问题交给图的最短路径算法，搜索过程中把代价算进去，用剪枝和优先级让复杂度可控。这也是后面选择Dijkstra变体而不是枚举的根本原因：不是枚举不能做，而是它没法优雅地扩展到真实规模。

1.3 把换乘枢纽拆成多个状态

换乘是换乘算法的灵魂，必须单独拎出来解剖。普通人眼里的"人民广场站"是一个点，但在算法眼里，它其实是"L1线的人民广场站"和"L2线的人民广场站"两个状态叠在一起，中间有一条代价为换乘时间的虚拟连接。

这个视角转换非常关键：走到人民广场不叫到达，你得先明确自己到底是坐L1来的还是坐L2来的。从L1下车走到L2站台，是在同一个地理站点上的一次状态迁移，这个迁移要付出额外代价，包含步行、等车、可能的意外延误。

把换乘当成状态迁移，而不是原地停留，是后面扩展状态Dijkstra的核心思想。它天然能回答"换乘几次"的问题，也方便将来加入站内步行距离、换乘通道拥挤度等更精细的成本。可以说，整个算法的难度不在Dijkstra本身，而在于能不能把"换乘"这个动作建模得足够准确。

2. 数据结构选型：邻接表、顺序表与并集操作

图模型确定后，就轮到数据结构选型。这部分看起来基础，实际上直接影响代码可读性和运行效率。我对每个选择都会解释一下原因，避免读者照着代码敲完却不知道为什么要这样设计。

2.1 稀疏图用邻接表，别迷信邻接矩阵

地铁网的拓扑结构是典型的稀疏图：站点几百个，区间边也就千把条。如果拿邻接矩阵来存，500个站点就要开25万个格子，其中绝大部分是无效的"不可达"标记，白白浪费内存。更关键的是，Dijkstra松弛时要遍历某个站点的所有邻居，邻接矩阵每次都得扫一整行，而邻接表直接顺着链表走一遍就行，天然省时间。

邻接表在C语言里的典型实现是"顶点数组 + 边链表"。每个顶点是一个结构体，里面放着站名和一条链表的头指针；链表的每个节点记录目标站点编号、线路编号、区间耗时，以及指向下一条边的指针。基本形态如下：

typedef struct Edge { int to; // 目标站点编号 int line; // 所属线路编号 int weight; // 区间耗时，单位：分钟 struct Edge *next; // 下一条边 } Edge; typedef struct { char name[20]; // 站名 Edge *first; // 邻接链表头 int lineMask; // 位标记：该站属于哪些线路 } Station;

这里有个容易被忽略的细节：每条边都要同时加入两个方向，也就是从u加到v、再从v加到u，否则图上会出现诡异的"单向轨道"。我用头插法建链表，因为建图顺序不影响结果，而头插法的代码最简单，不用维护尾指针。

lineMask这个位运算标记，是给站点做"线路归属"快速判断用的。比如想知道人民广场是否经过2号线，只需要看lineMask & (1 << 1)是否为真，O(1)就能完成，不需要遍历边链表。

2.2 用顺序表存站点集合，顺手解决线路并集

图结构负责"导航"，但程序里还经常需要回答另一类问题："1号线经过哪些站""1号线和2号线一起能覆盖哪些站""哪些站可以换乘"。这类问题涉及的是集合运算，和图遍历不是一回事，得额外维护线路站点集合。

C语言里最朴素的集合实现就是顺序表：一个数组存元素，一个整数存长度。数据量小的时候，查找就用线性扫描，完全够用。以500个站点、30条线路的规模为例，每条线也就几十个站，线性扫描每次几十次比较，性能根本不是瓶颈，没必要上哈希表或平衡树。

顺序表最有代表性的运算就是并集。两个线路的站点并集，直观理解就是"坐上这两条线，你总共能到达哪些站"。算法很朴素：先把第一个集合的元素全部复制进结果，然后遍历第二个集合，遇到结果里不存在的元素就追加到末尾。去重靠的是一个顺序查找，避免重复项。

这个操作看似基础，用途却很实际。比如规划新线路时，想知道它与既有线路能一起覆盖多大范围，并集一下就有答案；再进一步，两个线路站点集合的交集，恰恰就是换乘站的候选集。后面的完整代码里，我专门实现了seqUnion这个函数，还把两条线路的并集运行结果打印出来演示。

2.3 换乘权重的设定：把"走路+等车"算进成本

数据结构解决存储，算法解决搜索，但搜索时用的"代价"才是决定方案合理性的关键。地铁区间耗时我按一站3分钟来设，长区间可以给4到5分钟，这个弹性无所谓；真正需要用心设计的是换乘惩罚。

我在代码里把一次换乘的惩罚设成30分钟。这30分钟模拟了下车、步行到另一站台、等下一班车的完整过程。更重要的是，它是一个给算法的明确信号：能少换乘就少换乘。

为什么是30而不是5？因为一站才3分钟，如果换乘惩罚太小，算法会为了少坐一站而频繁换线，给出"坐一站、换一次、再坐一站"这种疯子方案。30分钟足够压住这种无效换乘，又不会大到让算法宁可绕一大圈也不换乘。这个值本质上是个超参数，实际工程里要结合换乘通道长度、发车间隔、拥挤度动态调整，但教学版本用固定值就能把原理讲透。

3. 换乘算法的核心思路与实现细节

数据结构就绪后，进入算法主体。这一章不直接甩代码，而是先把思路讲清楚。因为换乘算法最大的难点不是Dijkstra本身，而是想清楚"在一个需要换乘的图里，状态到底该怎么定义"。

3.1 无权图用BFS，带权图交给Dijkstra

如果所有区间代价都是1，找最少站数的路径用BFS就够了，一层层往外扩，第一次到达终点时的层数就是最少站数。但一旦引入换乘惩罚，每条边的代价都不一样了，BFS的队列就失效了——队列假设所有边代价相同，先入队的先扩展，代价模型复杂后这种假设不再成立。

Dijkstra的核心是"优先扩展当前已知距离最小的状态"。维护一个未确定集合，每次取出距离最小的那个，用它去松弛相邻状态。因为所有边权都是正数（地铁区间时间和换乘惩罚都大于0），所以Dijkstra的正确性有保证：一旦某个状态被标记为确定，它的距离就是最终最短距离，之后不会被更长的路径更新掉。

朴素Dijkstra的时间复杂度是O(V²)，V是状态数量。对于几百个站点的小型网络完全够用。后文在第5章讨论大规模场景下的堆优化方案，那属于性能增强，不影响这里的正确性。

3.2 扩展状态：把"当前在哪条线"放进搜索

普通最短路径的状态就是"当前位置"，但在换乘问题里，仅仅知道"我在人民广场站"是不够的。我是从L1线下来的，还是正坐在L2线上，决定了下一步要不要付出换乘代价。同一个站点，携带的"线路上下文"不同，未来的成本就完全不同。

因此必须把状态扩展成二元组：(站点编号, 线路编号)。

起点状态的处理要特别小心。起点站如果同时经过多条线路，那么它就有多个不同的初始状态，每个状态的距离都是0，比如"大学城, L2线"是0。因为起点站上车时，你既可以选择坐L2，如果这个站恰好也经过L3，那"大学城, L3线"同样可以是0。

从一个状态向外扩展时，规则只有两条：

• 沿着某条边走到邻站，如果边的线路编号和当前状态线路相同，那么代价就是边的权重；
• 如果边的线路编号不同，代价就是边的权重再加上换乘惩罚。

这样换乘代价被精确地嵌入在状态转移中。我不需要单独标记"这里是不是换乘站"，只要两个连续状态的站点相同、而线路编号不同，自然就知道发生了一次换乘。状态总数大约等于"站点数×线路数"，对地铁场景来说依然很小。

3.3 路径还原与换乘点识别

Dijkstra运行完，得到的是每个状态的最短距离。怎么还原成一条可读的出行线路？办法是每个状态在距离被更新时，记录前驱状态ID。

我把状态ID直接编码成一个整数：站点编号 * MAX_LINES + 线路编号。这样做的好处是不用开结构体数组来存前驱，一个二维prev数组就够了，内存占用小，调试打印也方便。

路径还原从终点状态倒着往回走，直到回到起点状态。然后把状态序列反转，从头开始，逐对检查相邻状态：

• 两个状态站点不同，说明是乘车区间，输出当前状态所在线路；
• 两个状态站点相同，说明发生了换乘，输出换乘后的线路。

这套逻辑稳定好使，而且天然能处理连续换乘的极端情况——比如某些站内跨三条线路的超级枢纽，连续两个相邻状态都站点相同、线路不同，就会依次输出两次换乘。

4. 完整C代码实现与运行效果

思路讲透了，进入实操环节。这一章的代码我按模块拆开讲，最后读者把它们按顺序拼接起来，就是一个能编译运行的完整程序。示例网络选了几条简单线路，故意不搞真实城市的复杂拓扑，把注意力集中在算法本身。

4.1 图结构与建图代码

先建立站点和边的数据结构，同时维护一个线路站点顺序表。这部分代码还包括seqUnion并集函数，对应前面第2.2节讨论的内容。

#include <stdio.h> #include <stdlib.h> #include <string.h> #define MAX_NODES 20 #define MAX_LINES 8 #define TRANSFER_PENALTY 30 #define INF 0x3f3f3f3f typedef struct Edge { int to; int line; int weight; struct Edge *next; } Edge; typedef struct { char name[20]; Edge *first; int lineMask; } Station; Station stations[MAX_NODES]; int stationCnt = 0; int stRailway, stCentral, stPeople, stTech, stAirport; int stUniv, stDowntown, stSports, stOcean, stOld, stNewLib; int addStation(const char *name) { strcpy(stations[stationCnt].name, name); stations[stationCnt].first = NULL; stations[stationCnt].lineMask = 0; return stationCnt++; } void addEdge(int u, int v, int line, int weight) { Edge *e = (Edge *)malloc(sizeof(Edge)); e->to = v; e->line = line; e->weight = weight; e->next = stations[u].first; stations[u].first = e; stations[u].lineMask |= (1 << line); e = (Edge *)malloc(sizeof(Edge)); e->to = u; e->line = line; e->weight = weight; e->next = stations[v].first; stations[v].first = e; stations[v].lineMask |= (1 << line); } void buildNetwork() { stRailway = addStation("火车站"); stCentral = addStation("中央广场"); stPeople = addStation("人民广场"); stTech = addStation("科技园"); stAirport = addStation("机场"); stUniv = addStation("大学城"); stDowntown = addStation("市中心"); stSports = addStation("体育中心"); stOcean = addStation("海洋馆"); stOld = addStation("老城区"); stNewLib = addStation("新区图书馆"); // 1号线：火车站 - 中央广场 - 人民广场 - 科技园 - 机场 addEdge(stRailway, stCentral, 0, 3); addEdge(stCentral, stPeople, 0, 3); addEdge(stPeople, stTech, 0, 3); addEdge(stTech, stAirport, 0, 4); // 2号线：大学城 - 人民广场 - 市中心 - 体育中心 - 海洋馆 addEdge(stUniv, stPeople, 1, 4); addEdge(stPeople, stDowntown, 1, 3); addEdge(stDowntown, stSports, 1, 3); addEdge(stSports, stOcean, 1, 4); // 3号线：老城区 - 火车站 - 体育中心 - 新区图书馆 addEdge(stOld, stRailway, 2, 4); addEdge(stRailway, stSports, 2, 6); addEdge(stSports, stNewLib, 2, 5); }

线路编号我用0、1、2分别代表1号线、2号线、3号线。代码里addEdge每次建边时同步更新两端站点的lineMask，这样后面构建顺序表时不用重新遍历边，直接通过位运算就能判断站点属于哪条线路。

4.2 Dijkstra状态扩展与路径还原代码

下面是算法的核心部分。扩展状态的技巧、路径还原、换乘次数统计都集中在这里。

int dist[MAX_NODES][MAX_LINES]; int visited[MAX_NODES][MAX_LINES]; int prev[MAX_NODES][MAX_LINES]; // 存前驱状态ID，-1表示没有前驱 int stateId(int s, int line) { return s * MAX_LINES + line; } void dijkstra(int start) { int i, j; for (i = 0; i < MAX_NODES; i++) { for (j = 0; j < MAX_LINES; j++) { dist[i][j] = INF; visited[i][j] = 0; prev[i][j] = -1; } } // 起点经过的所有线路都作为初始状态 for (j = 0; j < MAX_LINES; j++) { if (stations[start].lineMask & (1 << j)) { dist[start][j] = 0; } } while (1) { int bestDist = INF; int bestU = -1, bestLine = -1; for (i = 0; i < MAX_NODES; i++) { for (j = 0; j < MAX_LINES; j++) { if (!visited[i][j] && dist[i][j] < bestDist) { bestDist = dist[i][j]; bestU = i; bestLine = j; } } } if (bestU == -1) break; visited[bestU][bestLine] = 1; Edge *e; for (e = stations[bestU].first; e; e = e->next) { int newLine = e->line; int cost = e->weight; if (newLine != bestLine) { cost += TRANSFER_PENALTY; } int nd = bestDist + cost; if (nd < dist[e->to][newLine]) { dist[e->to][newLine] = nd; prev[e->to][newLine] = stateId(bestU, bestLine); } } } } int findBestEndLine(int end) { int best = INF; int bestLine = -1; int j; for (j = 0; j < MAX_LINES; j++) { if (dist[end][j] < best) { best = dist[end][j]; bestLine = j; } } return bestLine; } int countTransfers(int start, int end, int endLine) { int cnt = 0; int u = end, line = endLine; while (!(u == start && dist[u][line] == 0)) { int pid = prev[u][line]; if (pid == -1) break; int pu = pid / MAX_LINES; int pl = pid % MAX_LINES; if (pu == u && pl != line) { cnt++; } u = pu; line = pl; } return cnt; } void printPath(int start, int end) { int endLine = findBestEndLine(end); if (endLine == -1 || dist[end][endLine] >= INF) { printf("无法到达终点站 %s\n", stations[end].name); return; } int path[MAX_NODES * MAX_LINES]; int pathLen = 0; int u = end, line = endLine; while (!(u == start && dist[u][line] == 0)) { path[pathLen++] = stateId(u, line); int pid = prev[u][line]; if (pid == -1) { printf("路径还原失败：找不到前驱\n"); return; } u = pid / MAX_LINES; line = pid % MAX_LINES; } path[pathLen++] = stateId(start, line); int i; printf("完整路径：\n"); for (i = pathLen - 1; i >= 0; i--) { int su = path[i] / MAX_LINES; int sl = path[i] % MAX_LINES; printf("%s", stations[su].name); if (i > 0) { int nu = path[i - 1] / MAX_LINES; int nl = path[i - 1] % MAX_LINES; if (nu != su) { printf(" --(L%d线)--> ", sl + 1); } else { printf(" --换乘L%d线--> ", nl + 1); } } else { printf("\n"); } } int firstLine = path[pathLen - 1] % MAX_LINES; printf("\n出行方案：\n"); printf("从 %s 乘坐L%d线\n", stations[start].name, firstLine + 1); for (i = pathLen - 2; i >= 0; i--) { int su = path[i] / MAX_LINES; int sl = path[i] % MAX_LINES; int pu = path[i + 1] / MAX_LINES; int pl = path[i + 1] % MAX_LINES; if (su == pu && sl != pl) { printf("在 %s 换乘L%d线\n", stations[su].name, sl + 1); } } printf("到达终点 %s，全程耗时约 %d 分钟，换乘 %d 次\n", stations[end].name, dist[end][endLine], countTransfers(start, end, endLine)); }

stateId把二维状态压成一维整数，prev数组里存的全是这种ID。路径还原时再用除法和取模拆回站点编号和线路编号。这个"状态压缩"的小技巧，能让代码结构保持紧凑，同时又足够直观。

4.3 顺序表并集实现与主函数

最后是顺序表实现、线路站点集合构建、以及两组查询的入口。

typedef struct { int data[MAX_NODES]; int len; } SeqList; int seqFind(SeqList *list, int x) { int i; for (i = 0; i < list->len; i++) { if (list->data[i] == x) return i; } return -1; } void seqUnion(SeqList *a, SeqList *b, SeqList *result) { result->len = 0; int i; for (i = 0; i < a->len; i++) { result->data[result->len++] = a->data[i]; } for (i = 0; i < b->len; i++) { if (seqFind(result, b->data[i]) == -1) { result->data[result->len++] = b->data[i]; } } } void printSeqList(SeqList *list) { int i; printf("{ "); for (i = 0; i < list->len; i++) { printf("%s%s", stations[list->data[i]].name, i == list->len - 1 ? " " : ", "); } printf("}\n"); } void buildLineSets(SeqList *lineSets) { int i, j; for (i = 0; i < MAX_LINES; i++) { lineSets[i].len = 0; } for (i = 0; i < stationCnt; i++) { for (j = 0; j < MAX_LINES; j++) { if (stations[i].lineMask & (1 << j)) { lineSets[j].data[lineSets[j].len++] = i; } } } } int main() { buildNetwork(); SeqList lineSets[MAX_LINES]; buildLineSets(lineSets); printf("1号线站点："); printSeqList(&lineSets[0]); printf("2号线站点："); printSeqList(&lineSets[1]); printf("3号线站点："); printSeqList(&lineSets[2]); SeqList unionRes; seqUnion(&lineSets[0], &lineSets[1], &unionRes); printf("1、2号线站点并集："); printSeqList(&unionRes); printf("\n--- 查询1：大学城 -> 人民广场 ---\n"); dijkstra(stUniv); printPath(stUniv, stPeople); printf("\n--- 查询2：大学城 -> 机场 ---\n"); dijkstra(stUniv); printPath(stUniv, stAirport); printf("\n--- 查询3：老城区 -> 海洋馆 ---\n"); dijkstra(stOld); printPath(stOld, stOcean); return 0; }

buildLineSets根据lineMask把每个站归入对应线路的集合，本质上是对图信息的一次轻量聚合。seqUnion就是前面讨论的并集实现，先复制再查重，逻辑简单但完整。

4.4 运行结果与过程分析

把上面代码按顺序拼接，编译运行后，会得到类似下面的输出：

1号线站点：{ 机场, 科技园, 人民广场, 中央广场, 火车站 } 2号线站点：{ 海洋馆, 体育中心, 市中心, 人民广场, 大学城 } 3号线站点：{ 新区图书馆, 体育中心, 火车站, 老城区 } 1、2号线站点并集：{ 机场, 科技园, 人民广场, 中央广场, 火车站, 海洋馆, 体育中心, 市中心, 大学城 } --- 查询1：大学城 -> 人民广场 --- 完整路径： 大学城 --(L2线)--> 人民广场 出行方案： 从 大学城 乘坐L2线 到达终点 人民广场，全程耗时约 4 分钟，换乘 0 次 --- 查询2：大学城 -> 机场 --- 完整路径： 大学城 --(L2线)--> 人民广场 --换乘L1线--> 科技园 --(L1线)--> 机场 出行方案： 从 大学城 乘坐L2线 在 人民广场 换乘L1线 到达终点 机场，全程耗时约 41 分钟，换乘 1 次 --- 查询3：老城区 -> 海洋馆 --- 完整路径： 老城区 --(L3线)--> 火车站 --(L3线)--> 体育中心 --换乘L2线--> 海洋馆 出行方案： 从 老城区 乘坐L3线 在 体育中心 换乘L2线 到达终点 海洋馆，全程耗时约 44 分钟，换乘 1 次

这几个结果各有代表性。查询1是直达场景，验证基础路径输出；查询2是典型的一次换乘，算法在人民广场准确识别换乘点；最有意思的是查询3，老城区去海洋馆，理论上可以走"老城区→火车站→人民广场→市中心→体育中心→海洋馆"这条绕远路线，但算法选择了在体育中心直接换乘，全程只需要44分钟，比绕去人民广场的方案节省大量时间。这就是换乘惩罚权重在起作用：它让算法在"多坐几站"和"换一次线"之间做出了理性判断。

5. 实测中的坑与优化方向

代码跑通只是第一步，真正在真实工程里落地时，还有一堆细节会咬人。这一章记录我实际踩过的坑和对应的解决经验，全是教科书里不太会写的东西。

5.1 双向边、环线与lineMask的边界

最基础也最容易翻车的，是双向边漏加。addEdge里如果只加一个方向，Dijkstra搜出来的路径就是"单向可达"，看起来像地铁线路只允许单向乘坐，非常诡异。我自己的习惯是写完建图函数后，先打印每个站点的邻接表，肉眼扫一遍确认每个区间都出现了两次。

环线是另一个隐蔽的坑。环线是首尾相接的，如果不把最后一站和第一站之间的边加上，环线就被硬生生切成了一段"断头路"，绕一圈坐回原点的合法路径会永远搜不到。示例网络里虽然没有环线，但真实城市基本都有，建图时必须留意。

lineMask的位移操作也有边界问题。我用1 << line标记线路归属，如果实际线路数小于MAX_LINES，没问题；但如果线路编号超出MAX_LINES，位移就会越界导致未定义行为。所以MAX_LINES必须留足余量，或者在建图时加一个"线路编号合法性"断言。

5.2 大规模网络的性能优化方向

朴素Dijkstra在示例规模下毫秒级完成，但真实城市的地铁网络站点多、线路密、查询频率高，必须做优化。

最直接的优化是用优先队列（小顶堆）替代每次线性扫描找最小状态，复杂度从O(V²)降到O(E log V)。E是状态之间可达边的数量。在这个算法里，V约等于"站点数×线路数"，E约等于"边数×线路数"，规模依然是可控的。

更进一步的做法包括：

• 双向Dijkstra：从起点和终点同时搜，两个方向在中途相遇即可停止。对单次查询能省一半左右的时间。
• A*启发式搜索：引入"当前站到终点站的直线距离"作为启发函数，让搜索更有方向性。
• 预处理换乘表：如果是固定的离线地图，可以提前把热门站对之间的最优路径算好，查询时直接查表，响应时间近乎零。

工程系统里通常不是只跑一个Dijkstra就完事，而是叠加了多种策略。但不管怎么叠，核心思想仍然是从"状态定义"出发，控制搜索空间。

5.3 调试心得与几个实用建议

最后分享几条我在调试这类代码时总结出的经验，每一条都是真实换来的教训。

调试时先打印前驱表。如果某个终点状态的距离合理，但prev值指向了一个根本不存在的状态ID，十有八九是状态ID的编码和解码没对齐。建议单独写一个printf("state %d -> %d\n")的调试辅助函数，逐条核对。

INF的取值要当心。不要用INT_MAX当无穷大，因为松弛操作里有bestDist + cost，一旦bestDist取到INT_MAX，加上任何正数都会溢出成负数，距离比较瞬间乱套。我用的是0x3f3f3f3f，约等于10.7亿，足够大又不会溢出。

测试用例要从简单到复杂逐级递进：先测直达，再测一次换乘，再测多次换乘，最后测起点和终点不可达的情况。"终点站没有任何线路经过"是一个容易被忽略的输入，但用户完全可能输入一个不存在的站点名。代码里findBestEndLine返回-1就是处理的这个场景。

另外建议给每个站点加一个英文编号甚至拼音缩写，调试打印时用中文站名虽然直观，但在终端里对齐困难，容易出现排版错乱。我就是因为贪图中文站名好看，调试时多花了半小时去对齐表格。