企业官网建设流程全解析

这题我最早是在一次算法练习里碰到的，第一眼以为只是个Dijkstra模板题：城市间紧急救援，求最短路径而已。结果样例一跑，发现还要输出“最短路径条数”和“最大救援队数”，甚至要把具体路径打出来。我当时心里就想，这题表面是在考图的应用，实际是把Dijkstra算法从“求一个最短路”硬生生拔高到“在满足多个条件下维护一组状态”。如果你只是背模板，大概率会在最短路径条数这个点上卡住。这篇就把我完全调通这题的思考过程写下来，从题目拆解、状态设计、代码实现到边界陷阱，尽量让还没吃透Dijkstra的人也能顺着这套思路把代码写出来。

1. 这道题真正想考的不是模板：最短路径只是入场券

1.1 三个输出目标的层次关系

先把题意复述一遍。假设有N个城市，城市之间有M条双向道路，每条道路有长度。每个城市都驻扎着一定数量的救援队。现在给定起点S和终点D，要你从S出发到D，输出两样东西：第一行是最短路径条数、在所有最短路径里能集结到的最大救援队数量；第二行是满足“路程最短且救援队最多”的那条城市编号序列。

很多人一看到这里，就急着把“最短路径条数”理解成“救援队最多的那条路径算1条”，这是第一个大坑。题目说的是：先把所有长度等于最短距离的路径全找出来，数一数有多少条；然后在这么一大堆最短路径里，比较它们沿途能带上的救援队总数，取最大值；最后把这个最大值对应的那一条路径输出。这三个目标不是并列关系，而是层层筛选的关系——距离是第一优先级，距离相同才看救援队数量。

打个比方，这就好比打车去机场：先划定“最短路程”这个候选池，路程一样的情况下再比较谁的车内环境好。你不能为了环境好去绕远路，也不能因为环境差就否认这条最短路径“存在”这件事。题目要你统计的路径条数，统计的是整个最短路径集合，不是只统计环境最好的那一辆。

1.2 读懂样例之前，先问自己三个问题

我调这个题的时候，习惯先不看代码，而是拿笔对着题目问三个问题，答清楚了再动手：

第一，每条边是双向还是单向？通常城市间救援都按无向图处理，读入一条边要在邻接表里插两次。有些题不说明，但样例里能看出来——一条路能从a到b，也应该能从b到a，否则救援车没法原路返回。

第二，救援队数量怎么累计？题目给的是每个城市自己的队伍数，你从S出发，经过某个城市，就能把这个城市的救援队“捡”起来带着走。所以起点S自己的队伍数也是要算进去的。我一开始漏了这个，样例里S城市有20人，我初始化成0，结果输出差了一大截。

第三，最短路条数到底怎么定义？如果两条路的城市序列不同，即使长度一样，也算两条不同的最短路径。这里不谈“重边算不算多条”这种细节，题目里如果存在两条道路把同一对城市连接起来，并且长度相同，那它们在统计时也应该当作两条不同的路径来算。这个在后面的松弛逻辑里会自动处理。

这三个问题想明白，题目就已经读懂了一半。剩下的就是算法层面的扩展。

2. 状态设计：在Dijkstra的背包里多装三样东西

2.1 为什么要扩展Dijkstra而不是换算法

经典Dijkstra算法维护一个dist数组，做的是单源最短路：每轮从未访问的点里选一个dist最小的点u，用u去松弛它的邻居v。整个过程基于一个核心性质——所有边权非负，所以已经确定距离的点不会再被更小的值更新。这个性质非常重要，因为我要统计路径条数、累计救援队人数，就必须保证dist[u]在u被选中时已经“尘埃落定”，不然所有计数都是空中楼阁。

有些同学看到要统计多条最短路径，第一反应是改成SPFA或者用Floyd。SPFA在负权图上能用，但这里边权都是正整数，没有负权优势；Floyd能跑出所有点对最短路径，但O(N^3)复杂度在N稍大时就很浪费，而且你还需要额外处理路径条数统计和重建，代码量会失控。在正权图上做单源多目标统计，Dijkstra的“单调扩展”特性反而是最适合的——因为它天然保证每个点的状态只被最终确定一次，计数不会乱。

2.2 四个辅助数组的分工与初始化

除了常规的dist数组，这道题需要额外开四个数组，它们的含义必须一开始就分清：

先说cnt[S]=1，这是最容易被忽略的。从S到S本身，路径长度为0，这条路径确实存在，所以条数要初始化为1。如果这里写成0，后面所有cnt[v]=cnt[u]的继承关系会全部变成0，最后输出永远是0条路径。

再说team[S]=城市S的救援队数。为什么不是0？因为你到达S之后，就已经可以带上S的救援队出发了。起点城市的队伍是要参与集结的。这一点别想当然，我确实见过有人把起点队伍数设成0，理由是“出发前自己城市的队伍不算集结”，但题目语义不是这样，它问的是从S到D的整条路径上能集结到的最大队伍数，起点当然包含在内。

前驱数组pre只需要存一条路径的信息，也就是当前“距离最短且队伍最多”的那条路径。如果之后发现一条相同距离、更多队伍的路径，就覆盖pre；如果相同距离、队伍数也一样，优先级低，就不覆盖。

2.3 松弛操作里真正的“决策”发生在哪一行

Dijkstra的每轮松弛，在经典版本里只有一种情况：dist[v] > dist[u] + w，然后更新dist[v]。这道题把单一的更新动作拆成了两个分支：

第一分支，dist[v] > dist[u] + w，说明找到了一个更短的到达v的路径。此时等于把v之前的统计全部推倒重来：dist[v]要更新，cnt[v]要继承cnt[u]，team[v]要更新为team[u]+城市v的救援队数，pre[v]=u。

第二分支，dist[v] == dist[u] + w，说明这条路和已有最短路径一样长。此时不能推倒重来，只能追加：最短路径条数要累加，即cnt[v] += cnt[u]；同时比较救援队总数，如果team[u]+城市v的救援队数大于team[v]，就把team[v]和pre[v]更新掉。

这两行分支的先后顺序不能换，必须先处理“更短”，再处理“等长”。因为“等长”累加的前提是当前dist[v]已经是最短距离；如果先做等长累加，下一步又发现一个更短路径，那刚才累加的条数和比较都是白做，还得恢复回去。按顺序写，逻辑最干净，也不容易漏状态。

3. 完整实现：从邻接表到路径回溯的一步步代码

3.1 完整代码（C++，朴素版）

这道题城市数量一般在几百这个量级，朴素版Dijkstra的O(N^2+M)完全够用，没必要上堆优化，代码还更好读。以下是当时跑通的完整实现：

#include <bits/stdc++.h> using namespace std; const int INF = 0x3f3f3f3f; int n, m, s, d; vector<int> cityTeam; vector<vector<pair<int, int>>> graph; vector<int> dist; vector<int> cnt; vector<int> team; vector<int> pre; vector<bool> visited; void dijkstra() { dist.assign(n, INF); cnt.assign(n, 0); team.assign(n, 0); pre.assign(n, -1); visited.assign(n, false); dist[s] = 0; cnt[s] = 1; team[s] = cityTeam[s]; for (int round = 0; round < n; ++round) { int u = -1; for (int i = 0; i < n; ++i) { if (!visited[i] && (u == -1 || dist[i] < dist[u])) { u = i; } } if (u == -1 || dist[u] == INF) break; visited[u] = true; for (auto edge : graph[u]) { int v = edge.first; int w = edge.second; if (dist[v] > dist[u] + w) { dist[v] = dist[u] + w; cnt[v] = cnt[u]; team[v] = team[u] + cityTeam[v]; pre[v] = u; } else if (dist[v] == dist[u] + w) { cnt[v] += cnt[u]; if (team[v] < team[u] + cityTeam[v]) { team[v] = team[u] + cityTeam[v]; pre[v] = u; } } } } } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin >> n >> m >> s >> d; cityTeam.resize(n); for (int i = 0; i < n; ++i) { cin >> cityTeam[i]; } graph.resize(n); for (int i = 0; i < m; ++i) { int u, v, w; cin >> u >> v >> w; graph[u].push_back({v, w}); graph[v].push_back({u, w}); } dijkstra(); cout << cnt[d] << " " << team[d] << "\n"; vector<int> path; for (int cur = d; cur != -1; cur = pre[cur]) { path.push_back(cur); } reverse(path.begin(), path.end()); for (size_t i = 0; i < path.size(); ++i) { if (i > 0) cout << " "; cout << path[i]; } cout << "\n"; return 0; }

这个写法里有个细节：松弛邻居时，我没有显式检查visited[v]。因为你想想Dijkstra每轮取出的u已经是当前未访问集合里dist最小的点，边权又都是正的，一个已经被访问过的点不会真的再从u这里发现“更短”路径。等长分支在正边权下也不会碰到已访问点，所以不判断反而让代码更干净。如果你习惯显式写if (visited[v]) continue，也没问题，两种写法在这道题的数据下结果一致。

3.2 代码中几个容易被忽略的细节

第一个细节是邻接表的类型。我用的vector<vector<pair<int,int>>>，pair的first是邻居编号，second是边长。双向边一定要插两次，否则救援车只能单向走，样例都不一定过。

第二个细节是输出第一行的顺序。题目要求先输出最短路径条数，再输出最大救援队数，千万别写成“队伍数 条数”。我第一次提交就是把顺序看反了，白送一个WA。

第三个细节是路径回溯。pre[d]存的是路径上d的前一个城市，一路顺着pre走回s，再把数组reverse一下输出。这里要注意pre[s]我初始化为-1，所以循环终止条件是cur != -1。如果你的城市编号从0开始，-1做终止符正好，不会跟正常城市编号撞车。

第四个细节是取点的break条件。如果u仍然为-1，或者dist[u]=INF，说明剩下的点全部不可达，直接退出，没必要继续空转。虽然题目保证S到D可达，但写成防御性代码总好过RE。

4. 踩坑与边界：等长路径的计数为什么总写错

4.1 最经典的坑：cnt[v]是继承不是自增

我在练习群里看到很多人在等长分支里写的是cnt[v]++甚至cnt[v] = 1，样本一跑就错。我们来手动推一个反例，假设S到T有两条最短路径，一条经过A，另一条经过B：

S -> A -> T S -> B -> T

如果从S到A有一条路径，从S到B也有一条路径，那么从S到T的最短路径条数应该是2。用cnt[T] += cnt[A] + cnt[B]这个逻辑，cnt[T]最终等于2，正确。但如果你写cnt[T]++，那T只能被递增1次，哪怕A和B各自又带出多条分叉，你也只会统计到1条，漏得离谱。

更典型的场景是分支组合：S到A有2条最短路径，S到B有3条最短路径，而A和B都通过一条等长边连到T，那么从S到T经过A或B的最短路径总数应该是2+3=5。这就是为什么等长时一定要累加cnt[u]，而不是加固定值1。你可以把cnt理解成“路径方案数”，方案数要从上一跳的方案数继承过来，不是每跳一个城市就+1。

另外，当出现更短路径时，cnt[v]应该被覆盖成cnt[u]，而不是在原来的基础上累加。因为原来的那些路径已经不再是“最短”了，统计必须重置。每次看到dist[v]被更新，我脑子里就默认要执行一次“清零重来”，这样写才不会把新旧统计混在一起。

4.2 起点终点重合与不可达的情况

如果S和D一样，答案其实已经写死在初始化里了：最短路径条数是1，最大队伍数是城市S自己的队伍数，路径输出就是S本身。你不需要特判，Dijkstra第一轮会选中S，标记访问后，后续轮次里剩余点要么不可达，要么距离更大，cnt[D]和team[D]不会被修改。最后输出依然正确。不过如果你写了提前判s==d的逻辑，可以省下一点时间，也不算错。

不可达的情况，题目基本不会给，因为题目保证救援一定可行。但我在实际调试时会把dist[d]等于INF的情况单独列出来打一句调试信息，避免路径数组里出现一堆无意义的-1导致段错误。防御性处理一下没坏处。

4.3 重边、双向边与零权边

重边在这题里是个隐藏考点。假设A到B存在两条道路，长度都是5，那么从A到B就应该有两条最短路径。我们的代码在读入时会给邻接表插入两条{A,5}的记录，松弛时第一次把dist[B]从INF更新成dist[A]+5，cnt[B]=cnt[A]；第二次因为dist[B]已经等于dist[A]+5，进入等长分支，cnt[B]累加一次cnt[A]。这样最终cnt[B]会变成两倍，正好把重边算成两条路径。这个行为是符合题目直觉的——两条不同的道路，即使长度相同，也是两种救援方案。

零权边就要多留个心眼。Dijkstra在零权边存在时，路径计数会涉及“同距离节点的处理顺序”，处理不当可能漏计或重计。竞赛里这类题通常给正整数边权，所以我在这篇里不展开。如果你自己设计测试数据，别刻意放一堆0边进去为难自己的代码。

4.4 救援队变多不等于路径变长：决策是“先短后多”

还有一个看起来很低级、但实际很容易钻牛角尖的困惑：如果有一条路径长度只比最短路径长1，但救援队数量多出一倍，要不要选它？答案是“不选”。题目已经把优先级写得明明白白——最短路径条数统计的是全体的最短路径，救援队数量的比较领域局限在“最短路径”这个圈子里。我一度犹豫要不要把“长度+队伍数”算成一个加权总分，后来发现一旦加权，就无法保证“路径长度优先”这个硬约束，甚至可能选出一条不是最短的路径，直接全错。

所以状态设计里，dist和team是分开维护的，只在等长时才比较team。这个“双关键字比较”的思路，比任何加权求和都要稳。

5. 从25分题到真实救援调度：这个模型能走多远

5.1 最短路径计数：图论里被低估的能力

别看“最短路径条数”只是这道题的附加输出，它在真实场景里其实非常常用。比如网络路由中，两个节点之间存在多条等价路径，运维需要知道到底有几条，才能在故障时做负载均衡；社交网络里研究“六度分隔”时，两个人之间有多少条等长的最短联系链，也是这类问题。Dijkstra本身只是给出dist，但通过cnt数组的递推，它就能一并告诉你“最短路有几条”。这个能力在教科书上很少被展开讲，一旦用起来会发现特别顺手。

cnt递推之所以能成立，完全依赖Dijkstra处理节点的顺序：从近到远。每个点被取出时，所有可能到达它的更短路径来源都已经处理完毕，cnt[u]才是最终值。这就是为什么我前面强调不能用SPFA替代——SPFA的更新顺序不保证这样的单调性，统计容易乱。

5.2 双关键字与更多真实约束的引入

“先看距离，再看队伍数”其实就是双关键字最短路。真实系统里的约束往往更多：道路可能拥堵、部分路段禁止通行、某些城市医院容量不足。这些都可以抽象成更复杂的边权或点权，但决策框架是一样的——维护多个候选值，按照优先级逐层比较。比如你还可以给team数组再加一个维度，比如“经过的最多医院数”，那等长分支里就要连续比较两轮。

如果你要处理的是“救援队可以从多个城市同时出发”的场景，还可以加一个虚拟源点，把它和所有可出发城市连一条长度为0的边，照样跑一遍Dijkstra。这类扩展在工程中很常见，本题的代码结构完全能承接住。

5.3 从算法到工程：一条路线的落地

最后聊几句真实的地图导航。很多人以为导航就是Dijkstra或者A*，区别只在启发函数。这类“输出具体路径”的题目，其实模拟了导航里“路线回显”的环节——计算完最短距离还不够，必须把一条路径以经纬度序列或城市序列的形式展示出来。pre数组就是路线回显最朴素的实现。真实引擎里还要考虑实时路况和转向限制，本质上是在这张图上做更复杂的边权动态更新，再重新跑最短路。你看，一道25分的题目模型，背后藏着的是一整套路径规划系统的基本盘。

我个人的实操体会是，做这类“模板题加变体”最有效的办法，不是直接背代码，而是先把状态数组写下来，手动推一遍样例的松弛过程。比如我自己举一个微型例子：S=0，D=3，0到1长度1，0到3长度3，1到3长度2，1到2长度2，2到3长度1，城市队伍数分别是20、30、40、10。手动模拟时你会发现dist[3]第一次被0直接更新为3，队伍30；等1被取出后，dist[3]不变但cnt[3]累加成2，队伍更新成60。就这么一推，等长累加和队伍比较的语义就全清楚了，代码反而不容易写错。如果这篇的步骤能帮你少踩一两个坑，那这25分拿得就值了。