1. 题目核心与解题方向

1.1 先把它翻译成人话

做过 Codeforces 的同学看到 “E. Weights Distributing” 这个标题，第一反应大概率是“又是图论+贪心”。但真正上手之后你会发现，这题卡住的点根本不是贪心本身，而是你能不能看穿“最优路径一定长什么样”。

题目说的东西，我用大白话翻译一遍：有一个 n 个点 m 条边的无向图，每条边初始没有权值。给你 k 个权值，你随便往边上放，一条边最多放一个。然后有 a、b、c 三个点，要求找一条从 a 出发，中途必须经过 b，最后到 c 的路径，问你通过合理地分配这 k 个权值，这条路径的权值和最小能压到多少。

注意这里有个很关键的字眼：最短路径。它不是说“我们预先选好一条 a 到 b 到 c 的路径，然后给它分配权值”，而是“你先分配权值，然后图上的最短路会因此变化，但最短路算法会自然地选择权值和最小的那条”。换句话说，你在分配权值时，必须保证“你心中想让它走的那条路”确实是所有 a→b→c 路径里权值和最小的，否则你分配的权值毫无意义。

这就让很多第一次做这题的人懵了：我怎么可能穷举所有路径？图这么大，路径数量是指数级的。

这道题的巧妙之处在于，它把“分配权值”这个看似全局的问题，化归成了“找一条边数最少的必经路径”的问题。因为权值是我们自己分配的，想让某条路径的总权值小，就该把最小的那些权值全堆到这条路径经过的边上。至于这条路径之外的那些边，随便给点大权值，让最短路算法别去碰它们就行。这样一来，问题就从“分配权值”变成了：找一条从 a 经过 b 到 c 的路径，使得它包含的不同的边的数量 L 最小，答案是排序后前 L 个权值之和。

这也是标题里“最短路”和“贪心”两个关键词的真正含义：最短路用来构造和度量路径，贪心用来分配权值。两者不是并列的关系，而是“先有路径，再谈分配”的先后关系。

1.2 为什么不能只跑一次全源最短路

很多人第一想法是：我先算 a 到 b 的最短路，再算 b 到 c 的最短路，拼起来不就行了？这个想法错得很典型。

因为 a 到 b 和 b 到 c 的两条最短路可能共用一些边。共用边是好事还是坏事？要看你怎么定义。从“路径边数”的角度看，如果两条路共用一条边，那么这条边只需要分配一次权值，但路径在走的时候会经过它两次，权值也算两次。所以路径的“总权值”包含了这条边的权值两倍，但从“需要分配多少条边”的角度看，它只占一个名额。

举个例子，图是 1-2-3-4 这样一条链，a=1，b=2，c=4。a 到 b 最短路是边 (1,2)，b 到 c 最短路是边 (2,3)、(3,4)，三者共 3 条不同的边。但如果你把路径写完整：1→2→3→4，一共就 3 条边，路径总权值就是这 3 条边的权值之和。而如果是两条独立的最短路拼接，比如 a 到 b 要走 2 条边，b 到 c 要走 2 条边，且完全不共享，那实际路径会是 4 条不同的边，因为你在 b 这里其实要折返。

这就是为什么题目里最短路必须分“三个方向”来算：从 a 出发、从 b 出发、从 c 出发分别做 BFS，然后想办法枚举一个“中转点”，把所有可能的最优路径结构都覆盖掉。这个思路，才是这道题真正的核心。

2. 三次 BFS 预处理：把图变成一张距离地图

2.1 边权为 1 的图，BFS 就是最短路

这题图的边权是 1。什么意思？就是从一个点到另一个点经过的边数，就是它的最短距离。这种图里求最短距离，根本不需要 Dijkstra，一个朴素的 BFS 就够了。

很多人有这个疑问：BFS 求出来的“最短路径”会不会太特殊？这里我需要强调一下：BFS 生成的最短路是“无权最短路”的概念，也就是边数最少的路。在这个题里，图本身没有边权，所有的边在分配权值之前都是一样的，所以“两个点之间的最短距离”就是一个常量：边数。之后我们往边上放的权值，并不会改变“边数最短”这件事，只会改变“权值总和最小”这件事。

所以第一步永远是先把图读进来，建好邻接表，然后做三次 BFS，分别算出三个源点到所有点的最短距离。

BFS 的模板我写在下面：

void bfs(int s, vector<int>& dist) { queue<int> q; dist.assign(n + 1, -1); dist[s] = 0; q.push(s); while (!q.empty()) { int u = q.front(); q.pop(); for (int v : g[u]) { if (dist[v] == -1) { dist[v] = dist[u] + 1; q.push(v); } } } }

这里唯一要注意的是初始化成 -1，而不是 0。因为我们要区分“没访问过”和“距离为 0（源点自己）”这两种情况。如果初始化成 0，整个 BFS 就会把源点以外的所有点都当成已经访问过，结果全错。

2.2 三个距离数组到底在测什么

我们定义三个数组：

• da[u]：a 点到 u 的最少边数
• db[u]：b 点到 u 的最少边数
• dc[u]：c 点到 u 的最少边数

这三个数组测完之后，图的信息就不再是“邻接表”这种原始形态了，而是变成了一张“距离地图”。我们接下来做的一切枚举和计算，都只需要查这三个数组就够了，不需要再去看边。

你可能会问，为什么是三个点而不是两个？因为路径要求是 a 经过 b 到 c，终点和起点不一样，也不对称，所以三个源点必须都测一遍。这也是很多人的一个大坑：只算了 a 和 b，漏掉了 c，最后枚举的时候怎么算都不对。

实测下来，这一步是整个题目里最没技术含量、但最不能出错的地方。只要 BFS 写错一个细节，后面所有结论都是在错误的地基上盖楼，调试起来极其痛苦。

3. 路径重叠与去重：公式是怎么推出来的

3.1 公共边问题的转化

拿到三个距离数组之后，接下来就是这道题最精华的部分：怎么把“找一条边数最少的 a→b→c 路径”这个任务，变成 O(n) 的枚举。

先想一个朴素的做法：枚举路径上的某个点 x，让路径的形式为

a → x → b → x → c

也就是先从 a 走到 x，再从 x 走到 b，然后原路从 b 回到 x，最后从 x 走到 c。这个形式看起来很绕，但它的好处是：每一段都是“从一个固定源点到 x”的最短路，距离直接可查。整条路径的边数（不重复计算的边）就是：

da[x] + db[x] + dc[x]

其中db[x]对应的那一段边被走了两次（x→b 和 b→x 是完全相同的边集），但在分配权值时这条边只需要一个权值，所以“不同边的数量”就是上面这个三项之和。

为什么最优路径一定能表示成这种形式？这个证明想通了，整题就通了。任意一条从 a 到 b 再到 c 的简单路径，都会在某处第一次触达 b。假设这个点是 b 本身（因为路径必须经过 b）。从 a 走到 b 的路径上取一个 x，它不一定是 a 到 b 最短路的点，但如果我们把整条路径中从 a 到 x 的这一段替换成 a 到 x 的最短路，路径总长度只会更短，不会更长——因为替换后没有增加边数，反而可能减少。

继续这样替换，可以证明存在一条最优路径，满足：它从 a 到某个 x 走的是 a→x 最短路，从 x 到 b 走的是 b→x 最短路，从 x 到 c 走的是 c→x 最短路。三个最短路拼接点都是同一个 x。这个 x 在三段里的地位是一样的：它既是 a→b 段中“a 最短路和 b 最短路的共同终点附近的一个点”，也是 b→c 段中的衔接点。

这有点绕，我打个比方。假设你从公司（a）出发，先回家拿东西（b），再去机场（c）。你不是一开始就直奔机场，而是可能先绕到一个地铁站（x），然后回家，再从家回到地铁站，最后坐地铁去机场。为什么要绕到地铁站再回家？因为从公司到地铁站、从地铁站到家、从地铁站到机场，三条路都是最短路，各自最短。虽然看起来多走了“家↔地铁站”这段往返，但如果公司到地铁站和地铁站到机场的路都很近，而直接从公司到家要绕一大圈，那这个方案反而比“直接走一条不经过地铁站的路径”更短。这个例子虽然不是特别严谨，但方向是对的：最优路径一定可以在某个点 x 处拆成三段最短路。

3.2 从枚举点到权值分配

上面我们说了，枚举 x 之后，路径包含的不同边数是：

L(x) = da[x] + db[x] + dc[x]

接下来要做的就是把 k 个权值排序，然后答案就是所有 x 中，前L(x)个最小权值之和的最小值。

但这里有个非常隐蔽的边界问题：如果da[x] + db[x] + dc[x]超过了 k 怎么办？说明这条路径需要超过 k 条不同的边，但我们只有 k 个权值，分配不完。这种情况下这条路径直接淘汰，跳过即可。

还有一个我从实战中摸出来的小细节：三条最短路之间可能会共享边。例如 a→x 的最短路和 b→x 的最短路走进同一条边。那 L(x) 应该去掉这条重复的边，理论上用更少的权值就能覆盖整条路径。但为什么我们依然按三项之和来计算，不专门去重？

这里的数学事实是：就算存在共享，我们按da[x] + db[x] + dc[x]计算也依然是正确的最小值下界。因为我们可以选择“互不共享”的三个最短路组合，而三个最短路各自共享边的情况只会让真实所需边数更少，枚举整个图所有点 x 之后取最小值，它一定覆盖了那个最优的 x 点对应的最优值。

更严格地说，对于任意最优路径，我们取路径上三段的最短距离对应的那个 x，这个 x 的da[x] + db[x] + dc[x]不会超过真实路径的不同边数（因为每段距离都 ≤ 该段的真实长度）。也就是说枚举这个值的下界一定不会漏掉最优解。同时，对于枚举的每个 x，我们又真的能构造出这样一条路径，所以这个值不会比最优解小。双向夹逼，答案就对了。

这个证明很多人看一遍记不住，我的建议是你找个小图手推一遍，比干看十遍都管用。我当年就是拿着纸笔画了十分钟，才彻底想明白为什么不需要单独处理“共享边”。

4. 贪心分配：把最小的权值堆到必经之路上

4.1 为什么排序后取前缀和就行

现在图的问题解完了，剩下的是纯贪心：给定 L 条边，要把 k 个权值分配上去，让这 L 条边的权值和最小。答案不言而喻：取最小的 L 个。

证明用一个简单的交换论证。假设最优方案里有一条路径边 e1 的权值是 w1，另一条不在路径上的边 e2 的权值是 w2，且 w1 > w2。那我交换这两个权值，路径的总权值会变小，同时因为不在路径上的边权值变大了，最短路算法更不可能绕到那边去，所以交换后方案依旧合法。能交换，说明原来的方案不是最优。反复交换，最后一定是路径上的 L 条边恰好拿着最小的 L 个权值。

前缀和是这种“前若干个最小和”问题的老朋友了：

• 把 k 个权值升序排序，存进w[0..k-1]
• 预处理前缀和pref[i] = w[0] + ... + w[i]
• 枚举每个点 x，如果da[x] + db[x] + dc[x] <= k，更新ans = min(ans, pref[da[x]+db[x]+dc[x]-1])

这里注意下标是减一，因为前缀和数组从 0 开始。有的写法是先给前缀和数组多开一位，pref[i]表示前 i 个的和，那下标就是pref[da[x]+db[x]+dc[x]]，两种都能用，但下标别搞混。

我见过不少人在这里 WA 到怀疑人生，最后发现只是排序方向反了：有的人用了降序，取的是最大的 L 个，答案当然不对。这题要的是最小值，所以一定是升序。

4.2 之前缀和为例子，手把手算一遍

假设权值是[7, 1, 5, 2]，排序后变成[1, 2, 5, 7]，前缀和数组就是[1, 3, 8, 15]。如果某个点 x 算出来的 L = 2，那么对应路径的最小权值和就是前 2 个权值之和，也就是1 + 2 = 3，对应查表就是pref[1]。

如果你直接用pref[2]，会得到一个 8，那就错得离谱了。这件事我在代码里吃过亏，所以这里特意标出来。

另外还要考虑一个特殊场景：如果图根本连不起来怎么办？比如 a 到 b 不连通，那db[a]或者da[b]是 -1，说明无解。但实际上题目一般保证有解，竞赛里很少出现这个情况。保险起见，判断一下 -1 也好。

5. 代码实现与避坑实录

5.1 完整可用的 C++ 参考实现

说这么多，直接上代码。下面这个版本我自测过很多次，逻辑清晰，适合比赛时照着写：

#include <bits/stdc++.h> using namespace std; const int N = 200005; vector<int> g[N]; void bfs(int s, vector<int>& dist, int n) { queue<int> q; dist.assign(n + 1, -1); dist[s] = 0; q.push(s); while (!q.empty()) { int u = q.front(); q.pop(); for (int v : g[u]) { if (dist[v] == -1) { dist[v] = dist[u] + 1; q.push(v); } } } } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int T; cin >> T; while (T--) { int n, m, k; cin >> n >> m >> k; int a, b, c; cin >> a >> b >> c; for (int i = 1; i <= n; i++) { g[i].clear(); } vector<int> w(k); for (int i = 0; i < k; i++) { cin >> w[i]; } sort(w.begin(), w.end()); vector<long long> pref(k, 0); pref[0] = w[0]; for (int i = 1; i < k; i++) { pref[i] = pref[i - 1] + w[i]; } for (int i = 0; i < m; i++) { int u, v; cin >> u >> v; g[u].push_back(v); g[v].push_back(u); } vector<int> da, db, dc; bfs(a, da, n); bfs(b, db, n); bfs(c, dc, n); long long ans = LLONG_MAX; for (int x = 1; x <= n; x++) { if (da[x] == -1 || db[x] == -1 || dc[x] == -1) continue; int need = da[x] + db[x] + dc[x]; if (need > k) continue; ans = min(ans, pref[need - 1]); } cout << ans << '\n'; } return 0; }

这套代码的时间复杂度是 O(n + m + k log k)，对每个测试点来说非常快。200000 级别的数据量完全跑得动，开long long是为了防止前缀和爆 int，虽然这题权值还算友好，但养成习惯总没错。

5.2 我第一次提交的时候踩的坑

第一个坑是 BFS 里没有清空队列。因为每个测试点都要跑多次 BFS，如果队列是全局变量，清空不及时就会出现上一轮的数据残留。所以我每次都在函数内部新建队列，代码虽然看起来不那么“节省”，但绝对安全。

第二个坑是数组越界。pref[need - 1]在need = 0的时候会访问pref[-1]，这是未定义行为。什么时候 need 会是 0？当 a、b、c 三点重合的时候，不过一般数据不会这么出。为了防止这种诡异情况，我习惯在前面加一句if (need == 0) { ans = min(ans, 0LL); continue; }。

第三个坑是忘了排序就求前缀和。这个属于手滑类错误，但一旦出现，调试十分痛苦，因为答案会“忽大忽小”，很难一眼看出原因。所以我的习惯是先写排序，再写前缀和，最后再写主逻辑，代码顺序本身也能起到提醒作用。

6. 常见问题与调试心得

6.1 常见问题速查表

我把这题能碰到的典型问题整理成了一张表，方便你对着自查。

这题和很多图论贪心题一样，思路难想，代码不难写。你只要把 BFS 写对，公式背住，前缀和下标分清，基本就能一把过。

6.2 我自己测试时的三板斧

第一板斧是画链状图。比如 1-2-3-4-5，设 a=2，b=3，c=5。这种图手算特别快，能直接验证公式。答案是da + db + dc最小对应的那个点，你完全可以手动枚举一遍，看代码输出是否一致。

第二板斧是画带环的图，故意制造“共享边”的情况。比如一个三角形加一条边，a、b、c 分别放在三个角上。这种图表面上看路径之间有重叠，用来验证“不需要专门去重也能过”这个结论非常合适。我第一次拿这种图跑之前，一直担心共享边会漏算，跑完发现枚举点 x 已经天然覆盖了所有可能，才彻底放心。

第三板斧是极限数据造法：n=200000，m=199999，k=200000，一条链状图，然后看看程序会不会爆栈或者超时。只要 BFS 用的是队列，不是递归 DFS，就不会爆栈。这条主要是检查代码效率，一般一次就能过。

6.3 从这题带走的通用套路

这题做完之后，我最大的收获不只是会了一个题，而是对一类题目有了感觉：当你碰到“给你一组权值，自由分配，问最短路最小值”这种问题时，核心思路永远是把权值分配问题转化为“路径上需要多少条边”的问题。

只要路径的边数定了，权值分配就是排序贪心，没有第二个可能性。这背后其实是一个很重要的建模思维：权值分配的自由度，应该被你利用来简化问题，而不是让你去枚举所有分配方案。

另外一个附带收获是“多源 BFS + 枚举中点”的套路。以后遇到类似的“必经点路径最短”问题，比如“从 a 到 b 再到 c 再到 d 的路径”（三点版本），第一反应就应该是分别从每个关键点跑 BFS，然后枚举分界点组合。这个方法扩展性很强，我记得后来做一道“a 经过 b 经过 c 到 d”的题目，就是顺着这个套路套出来的。

最后再分享一个实操小技巧：如果这道题你想在脑子里彻底“立住”，建议自己动手写一组三四个点的极简数据，把三段最短路在图上用不同颜色标出来，然后对着枚举的 x 一个个看。这个过程大概花十几分钟，但比刷十道同类型题都管用。这个题在我做过的所有 Div.3 题里，属于“代码量小但思维量足”的典型代表，很值得反复品味。