企业官网建设流程全解析

学过图论的人都会遇到这么一道入门题：信息学奥赛一本通上的P1381“城市路”。题面很朴素，给你n个城市和m条道路，问从1号城市到n号城市的最短路径长度。很多人觉得它简单，只写一个朴素Dijkstra就过了，然后就把这道题扔了。实际上，这一题特别适合用来把四种最短路写法一次练熟——朴素Dijkstra、堆优化Dijkstra、Bellman-Ford、SPFA。我给学生讲这题的时候，会故意让他们用四种写法各交一遍，收获比刷十道同类题还大。下面我把四种做法的思路、代码和踩过的坑一起说一说。

1. 题目原型与四种做法怎么选

1.1 题面到底在问什么

先别急着写代码，花两分钟把题看透。P1381说的是有n个城市，编号从1到n，城市之间有m条路，路是无向的，所以从a能到b，从b也能到a，每条路有一个长度。要求输出从城市1到城市n的最短距离。如果1到n不连通，输出-1。

这个题面里没有说路是单向的，所以建图时要加两条边。很多新手第一次就挂在无向图上，只加了一条边，结果只有一半样例能过。另外，注意可能有多条路连接同一对城市，这时候要取最短的那条。重边看似麻烦，其实在松弛时自然会被处理，因为你拿着较短的距离去更新，较长的根本不会成为答案。

还有一个经常被忽略的边界：当n=1时，城市1就是城市n，最短距离应该是0。可别程序一跑，发现dis[1]还是INF就输出-1，那就错了。

1.2 为什么拿这道题练四种做法

既然是最短路，为什么我不直接讲Dijkstra，而是说四种做法？因为最短路模板题的意义不是让你背一个模板，而是让你理解不同算法的适用边界。

朴素Dijkstra能在稠密图上发挥优势，因为它的时间复杂度O(n^2)不依赖边数，图的规模再密都扛得住。堆优化Dijkstra在稀疏图上几乎无敌，复杂度O(m log n)，m是边数，n是点数，边少了自然快。Bellman-Ford能处理负权边，虽然慢，但是思路简单，还能用来检测负环。SPFA是Bellman-Ford的队列优化版，在随机图上的平均表现不错，但最坏情况能把你卡哭。

把这四种都写一遍，才算真正把图论最短路的基础打牢。我上课时的比喻是：朴素Dijkstra是步行，堆优化Dijkstra是骑车，Bellman-Ford是手动挡汽车，SPFA是自动挡汽车。你当然可以只开自动挡，但万一哪天车子给你换挡的权利，你却不知道变速器怎么工作，那就尴尬了。

另外，提到Floyd的同学要注意，Floyd是任意两点之间的最短路，复杂度O(n^3)，这种单源问题拿它做不是不行，是浪费。所以这里不把Floyd算进四种做法。

2. 朴素Dijkstra：邻接矩阵是基础

2.1 核心思想与代码实现

Dijkstra的核心是贪心：从起点出发，每次找到一个“当前距离最短且还没有确定最终答案”的城市，它就是这一轮确定下来的点。然后从这个点出发，尝试刷新其它城市的距离。因为每条边都是非负的，已经确定最短路的点不会再有更短的路径，所以这个贪心是对的。

如果你没写过，建议先画一个只有4个城市的小图，手跑一遍。比如1号到2号距离1，2号到4号距离3，1号到3号距离4，3号到4号距离1。第一步确定1号，刷新2号和3号；第二步选中2号，刷新4号为4；第三步选中3号，刷新4号为2？等等，1->3=4，3->4=1，所以4的路径是5。其实2号到4是3，1->2->4总长4，1->3->4总长5。所以确定顺序应该是1,2,4,3。这个过程多跑几遍，比死记代码强。

下面是一份邻接矩阵实现的朴素Dijkstra：

#include <bits/stdc++.h> using namespace std; const int N = 205; const int INF = 0x3f3f3f3f; int n, m; int g[N][N]; int dis[N]; bool vis[N]; void dijkstra() { memset(dis, 0x3f, sizeof(dis)); memset(vis, 0, sizeof(vis)); dis[1] = 0; for (int i = 1; i <= n; i++) { int u = -1; int minv = INF; for (int j = 1; j <= n; j++) { if (!vis[j] && dis[j] < minv) { u = j; minv = dis[j]; } } if (u == -1) break; vis[u] = true; for (int v = 1; v <= n; v++) { if (!vis[v] && g[u][v] != INF) { if (dis[u] + g[u][v] < dis[v]) { dis[v] = dis[u] + g[u][v]; } } } } } int main() { cin >> n >> m; memset(g, 0x3f, sizeof(g)); for (int i = 1; i <= m; i++) { int a, b, w; cin >> a >> b >> w; g[a][b] = min(g[a][b], w); g[b][a] = min(g[b][a], w); } dijkstra(); if (dis[n] == INF) cout << -1 << endl; else cout << dis[n] << endl; return 0; }

这里用0x3f3f3f3f做INF，是因为int是4字节，memset按字节填充后，每个字节都是0x3f，整个整数就是0x3f3f3f3f，约等于10^9。两个INF相加也不会溢出int，方便在松弛时做加法比较。

2.2 复杂度分析与适用场景

朴素Dijkstra的时间复杂度是O(n^2)。外层循环确定n个点，内层找最小值扫描一次，再扫描所有点做松弛，所以两重循环，常数很小。空间上需要开一个n×n的邻接矩阵，如果n比较大，比如10^5，矩阵根本开不下，所以它只适合n比较小的稠密图。

什么是稠密图？就是边数m接近n^2的图。比如n=1000，m=100000，甚至m=500000，邻接矩阵虽然还能开下，但用堆优化会觉得大材小用。反过来，n=100000，m=200000，这时候邻接矩阵开不了，而且O(n^2)稳超时，必须换堆优化。

在一本通这道题上，数据范围给得比较温和，朴素写法能过。但你要知道它能过不是因为最优，而是因为题目放水。我读题第一步一定先看n和m，如果n超过1万，我绝对不会写这个写法。

3. 堆优化Dijkstra：稀疏图的默认解

3.1 用优先队列替代线性扫描

朴素Dijkstra慢在哪里？慢在每次都要在dis数组里扫一遍找最小值，这个操作是O(n)的。改进的思路很简单：用一个优先队列维护当前所有“可能成为下一个确定点”的城市，堆顶就是距离最小的那个。每次弹出堆顶，如果它已经过时，就跳过；否则确定它，并用它更新邻接点，更新成功后把新的状态丢进堆里。

这样，取最小值的代价从O(n)降到O(log n)，整体复杂度变成O(m log n)。这里的m是松弛操作的次数，实际是边数的常数倍。

代码：

#include <bits/stdc++.h> using namespace std; const int N = 100005; const int INF = 0x3f3f3f3f; struct Edge { int v, w; }; int n, m; vector<Edge> adj[N]; int dis[N]; void dijkstra() { memset(dis, 0x3f, sizeof(dis)); dis[1] = 0; priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq; pq.push({0, 1}); while (!pq.empty()) { int d = pq.top().first; int u = pq.top().second; pq.pop(); if (d != dis[u]) continue; for (int i = 0; i < (int)adj[u].size(); i++) { int v = adj[u][i].v; int w = adj[u][i].w; if (dis[u] + w < dis[v]) { dis[v] = dis[u] + w; pq.push({dis[v], v}); } } } } int main() { cin >> n >> m; for (int i = 1; i <= m; i++) { int a, b, w; cin >> a >> b >> w; adj[a].push_back({b, w}); adj[b].push_back({a, w}); } dijkstra(); if (dis[n] == INF) cout << -1 << endl; else cout << dis[n] << endl; return 0; }

这里最关键的一行就是priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;。因为优先队列默认是最大堆，而我们需要最小堆，所以要加greater<pair<int,int>>。很多人第一次写就忘掉，导致每次弹出来的是距离最大的点，跑出来的答案完全是错的。

3.2 细节：重边、自环、判重

堆优化Dijkstra最大的坑是“旧状态”的处理。一个点可能在松弛过程中被更新多次，每次更新都会向堆里丢一个pair。比如1号点从距离0更新到0，之后又可能被某个更短路径再次更新？注意，Dijkstra中一个点一旦被确定，距离不会更小。但在它确定之前，可能先进堆多次。比如起点1先通过2号更新到3号，距离10，后来又通过4号更新到3号，距离5，那么堆里就有(10,3)和(5,3)。如果不在弹出时判断if (d != dis[u]) continue;，那么(10,3)被弹出时会当作有效状态再处理一遍，虽然最终答案可能还是对的，但多做了很多无用功，甚至可能因为处理顺序导致复杂度退化。

重边在这种情况下不需要特别处理。因为松弛时只有更小的距离才会更新，所以较长的重边天然会被忽略。自环也是，正权自环不会让距离变小，负权自环那属于贝尔曼家族的领域了。

另外，无向图建边一定要双向。我见过一个学生用堆优化做这题，只加了adj[a].push_back({b,w})，忘了加反向边。结果样例能过，因为样例可能刚好只需要从1到n沿一个方向走，但测试数据里一旦需要走回头路，直接WA。

4. Bellman-Ford：带负权的“笨办法”

4.1 松弛n-1轮的原因

Dijkstra不能处理负权边，这是它的死穴。为什么？因为已经确定最短路的点可能因为一条负边被改变。比如起点到A距离5，到B距离3，但B到A有一条-4的边，那A的最短路其实是-1。Dijkstra第一次确定B，第二次确定A，这个例子不会错，但构造更复杂的例子就能让它错。所以遇到负权边，需要换思路。

Bellman-Ford的做法特别直白：对所有边做“松弛”，一共做n-1轮。每一轮里，对于每条边(u,v)，尝试用dis[u] + w去更新dis[v]；对于无向图，还要用反方向再更新一次。为什么是n-1轮？因为一条最短路径上最多只能有n-1条边，如果路径上有n条边，那必然有重复点，去掉环之后路径只会更短。所以每轮松弛至少能把一条边对应的距离固定下来，n-1轮足够找到所有最短路。

代码如下：

#include <bits/stdc++.h> using namespace std; const int N = 100005; const int M = 100005; const int INF = 0x3f3f3f3f; struct Edge { int a, b, w; }; int n, m; Edge e[M]; int dis[N]; void bellman_ford() { memset(dis, 0x3f, sizeof(dis)); dis[1] = 0; for (int i = 1; i < n; i++) { bool flag = false; for (int j = 1; j <= m; j++) { if (dis[e[j].a] + e[j].w < dis[e[j].b]) { dis[e[j].b] = dis[e[j].a] + e[j].w; flag = true; } if (dis[e[j].b] + e[j].w < dis[e[j].a]) { dis[e[j].a] = dis[e[j].b] + e[j].w; flag = true; } } if (!flag) break; } } int main() { cin >> n >> m; for (int i = 1; i <= m; i++) { cin >> e[i].a >> e[i].b >> e[i].w; } bellman_ford(); if (dis[n] == INF) cout << -1 << endl; else cout << dis[n] << endl; return 0; }

这个代码和Dijkstra比，最大的优势是思路简单，不需要优先队列，也不需要判断是否访问过。代价是慢，O(nm)。如果n是1000，m是10000，那要跑一千万次，勉强能接受；但如果n是100000，m是200000，直接超时到天荒地老。

4.2 如何用它判负环（本题不适用但是扩展）

Bellman-Ford还有一个附带技能：判断图中是否存在负权环。方法是在n-1轮松弛结束后，再对所有边做一轮松弛。如果这一轮还能成功更新某个dis，就说明存在负环。

原因还是“最短路最长n-1条边”这个性质。如果还能松弛，说明路径可以无限变短，那一定有个环的权重之和是负的。写代码时，可以在bellman_ford函数后面加一个check：

bool check_negative_cycle() { for (int j = 1; j <= m; j++) { if (dis[e[j].a] + e[j].w < dis[e[j].b]) return true; if (dis[e[j].b] + e[j].w < dis[e[j].a]) return true; } return false; }

不过要注意，我这里存的是无向边，所以每条边按两个方向检查。无向边一旦出现负权，就相当于同时存在两个方向的负权边，立刻构成负环。所以Bellman-Ford处理负权时，通常默认是有向图。P1381没有负权，所以这个扩展在这题用不到，但以后做带负权边的题目会用上。

5. SPFA：队列优化的浪漫与陷阱

5.1 实现细节与SLF/LLL优化

SPFA是对Bellman-Ford的改进。Bellman-Ford每轮都要扫描所有边，但很多时候大部分边并没有被松弛成功。SPFA的思路是：只有那些在上一轮被更新过的点，才可能在下一轮更新别人。所以用一个队列维护“待更新的点”，初始时把起点放进去，然后不断取出队首，遍历它所有出边，如果能松弛别人，就把那个点放进队尾。

代码：

#include <bits/stdc++.h> using namespace std; const int N = 100005; const int INF = 0x3f3f3f3f; struct Edge { int v, w; }; int n, m; vector<Edge> adj[N]; int dis[N]; int relaxed[N]; // 记录松弛成功次数 bool inq[N]; bool spfa() { memset(dis, 0x3f, sizeof(dis)); memset(inq, 0, sizeof(inq)); memset(relaxed, 0, sizeof(relaxed)); dis[1] = 0; queue<int> q; q.push(1); inq[1] = true; while (!q.empty()) { int u = q.front(); q.pop(); inq[u] = false; for (int i = 0; i < (int)adj[u].size(); i++) { int v = adj[u][i].v; int w = adj[u][i].w; if (dis[u] + w < dis[v]) { dis[v] = dis[u] + w; relaxed[v]++; if (relaxed[v] >= n) return false; // 存在负环 if (!inq[v]) { q.push(v); inq[v] = true; } } } } return true; } int main() { cin >> n >> m; for (int i = 1; i <= m; i++) { int a, b, w; cin >> a >> b >> w; adj[a].push_back({b, w}); adj[b].push_back({a, w}); } bool ok = spfa(); if (!ok) cout << "-1" << endl; // 实际题目不会出现 else if (dis[n] == INF) cout << -1 << endl; else cout << dis[n] << endl; return 0; }

这里relaxed[v]记录的是节点v被松弛成功的次数。正常情况下，一个点的最短距离最多被更新n-1次，如果更新到n次，说明存在负环。注意，在无向负权图里，SPFA一运行就会判负环，这符合理论。

如果你想让SPFA再快一点，可以加SLF优化：插入队首时，如果新节点的当前距离比队首还小，就插入队首。这个优化在随机图上效果不错，但治标不治本。还有LLL优化，取平均值判断，写起来更复杂，实战收益也有限。建议先把基础版本写对，再考虑优化。

5.2 卡SPFA的阴暗面

我必须要泼一盆冷水：SPFA的最坏复杂度是O(nm)，而且真的可以被构造数据卡死。最常见的就是网格图，每个点只和上下左右相连，起点在左上角，终点在右下角。这种图里，SPFA的队列会让大量节点反复入队出队，运行时间会让人怀疑人生。

所以很多出题人会专门设计数据卡SPFA。这也是为什么现在的主流建议是：如果题目说明边权非负，优先用堆优化Dijkstra，不要用SPFA去赌数据。如果题目有负权边，那就只能用Bellman-Ford或SPFA，但也要小心负环问题。这题P1381没有负权，用SPFA只是练手。你心里要清楚，它不是万能钥匙，只是一个有历史意义、思路漂亮的算法。

6. 四种做法对比与排错经验

6.1 复杂度与适用场景表格

我把四种做法的关键信息整理成一张表，方便你刷题时快速决定用哪个：

怎么选？第一步看n和m。n很大且m不大，堆优化Dijkstra是默认选项。n很小，怎么折腾都行。第二步看有没有负权边。有负权就避开Dijkstra，选Bellman-Ford或者SPFA。第三步看会不会有负环。负环意味着没有“最短路”，要先判出来。

这题是典型测正确性的，四种都能AC，但我建议你至少把堆优化Dijkstra练熟，因为它是未来竞赛最高频的写法。

6.2 常见Bug清单

最后给你一份我批改学生作业时随手记录的常见问题，基本都是真实踩过的坑：

1. 初始化漏边。邻接矩阵要memset(g,0x3f,sizeof(g))，输入时用min处理重边。如果忘了处理重边，后面松弛时可能用较大值覆盖较小值，直接让答案变差。

2. 无向图只建一条边。堆优化和SPFA的邻接表里，必须正反各加一次。Bellman-Ford里则必须对每条边做两个方向的松弛。

3. INF选择不当。用0x3f3f3f3f而不是0x7fffffff，原因前面说过，避免两个INF相加溢出。如果你用long long，就用0x3f3f3f3f3f3f3f3f，或者干脆1e18。

4. 堆优化忘记过滤旧状态。少了if (d != dis[u]) continue;，程序可能跑出正确结果，但耗时成倍增长。在极端数据下会超时。

5. 判断不可达的条件。用dis[n] == INF来判断，绝不能写成dis[n] == -1，因为你初始化的是一个大数，不是-1。

6. SPFA判负环的数组位置。有的同学把relaxed[v]++写在if(!inq[v])里面，只有入队时计数。这其实也能判，但可能漏掉节点已经在队列中的更新情况。我习惯写在松弛成功之后，逻辑更清晰。

7. 边界n=1。起点和终点相同，最短路是0。这个边界在四种算法里都要注意，尤其是在Bellman-Ford和SPFA里，如果起点就是终点，循环可能不会更新任何点，但你得输出0而不是-1。

我个人在实际操作中的体会是：不要把最短路算法当作模板死背，而是当成工具去理解。每学一个算法，就回到P1381这道城市路上，换一种写法重新提交一遍，对比时间和感悟。这样刷完，比盲刷二十道图论题都管用。

最后再分享一个小技巧：无论用哪种做法，开数组、建图、初始化这三个步骤做完，先跑一遍样例，再自己构造一个最小数据比如n=1或n=2, m=0验证边界，最后再交评测。这个习惯能帮你拦下至少一半不该有的WA。