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 这样一条链a1b2c4。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, vectorint dist) { queueint 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; vectorint g[N]; void bfs(int s, vectorint dist, int n) { queueint 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(); } vectorint w(k); for (int i 0; i k; i) { cin w[i]; } sort(w.begin(), w.end()); vectorlong 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); } vectorint 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 常见问题速查表我把这题能碰到的典型问题整理成了一张表方便你对着自查。问题现象可能原因解决方法答案偏大权值降序排序了改为升序排序答案比预期小很多前缀和数组下标写错确认pref[i]是从 0 还是从 1 开始有节点答案算出来是 0忘判 -1BFS 距离数组需要初始化为 -1大数据超时每次测试点没清空邻接表用 vector 并clear()每个点的邻接表答案始终是很大的数need k的情况被强行计入枚举时用continue跳过多组数据结果串了用了全局变量记录距离每次在函数内重新assign这题和很多图论贪心题一样思路难想代码不难写。你只要把 BFS 写对公式背住前缀和下标分清基本就能一把过。6.2 我自己测试时的三板斧第一板斧是画链状图。比如 1-2-3-4-5设 a2b3c5。这种图手算特别快能直接验证公式。答案是da db dc最小对应的那个点你完全可以手动枚举一遍看代码输出是否一致。第二板斧是画带环的图故意制造“共享边”的情况。比如一个三角形加一条边a、b、c 分别放在三个角上。这种图表面上看路径之间有重叠用来验证“不需要专门去重也能过”这个结论非常合适。我第一次拿这种图跑之前一直担心共享边会漏算跑完发现枚举点 x 已经天然覆盖了所有可能才彻底放心。第三板斧是极限数据造法n200000m199999k200000一条链状图然后看看程序会不会爆栈或者超时。只要 BFS 用的是队列不是递归 DFS就不会爆栈。这条主要是检查代码效率一般一次就能过。6.3 从这题带走的通用套路这题做完之后我最大的收获不只是会了一个题而是对一类题目有了感觉当你碰到“给你一组权值自由分配问最短路最小值”这种问题时核心思路永远是把权值分配问题转化为“路径上需要多少条边”的问题。只要路径的边数定了权值分配就是排序贪心没有第二个可能性。这背后其实是一个很重要的建模思维权值分配的自由度应该被你利用来简化问题而不是让你去枚举所有分配方案。另外一个附带收获是“多源 BFS 枚举中点”的套路。以后遇到类似的“必经点路径最短”问题比如“从 a 到 b 再到 c 再到 d 的路径”三点版本第一反应就应该是分别从每个关键点跑 BFS然后枚举分界点组合。这个方法扩展性很强我记得后来做一道“a 经过 b 经过 c 到 d”的题目就是顺着这个套路套出来的。最后再分享一个实操小技巧如果这道题你想在脑子里彻底“立住”建议自己动手写一组三四个点的极简数据把三段最短路在图上用不同颜色标出来然后对着枚举的 x 一个个看。这个过程大概花十几分钟但比刷十道同类型题都管用。这个题在我做过的所有 Div.3 题里属于“代码量小但思维量足”的典型代表很值得反复品味。
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 这样一条链a1b2c4。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, vectorint dist) { queueint 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; vectorint g[N]; void bfs(int s, vectorint dist, int n) { queueint 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(); } vectorint w(k); for (int i 0; i k; i) { cin w[i]; } sort(w.begin(), w.end()); vectorlong 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); } vectorint 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 常见问题速查表我把这题能碰到的典型问题整理成了一张表方便你对着自查。问题现象可能原因解决方法答案偏大权值降序排序了改为升序排序答案比预期小很多前缀和数组下标写错确认pref[i]是从 0 还是从 1 开始有节点答案算出来是 0忘判 -1BFS 距离数组需要初始化为 -1大数据超时每次测试点没清空邻接表用 vector 并clear()每个点的邻接表答案始终是很大的数need k的情况被强行计入枚举时用continue跳过多组数据结果串了用了全局变量记录距离每次在函数内重新assign这题和很多图论贪心题一样思路难想代码不难写。你只要把 BFS 写对公式背住前缀和下标分清基本就能一把过。6.2 我自己测试时的三板斧第一板斧是画链状图。比如 1-2-3-4-5设 a2b3c5。这种图手算特别快能直接验证公式。答案是da db dc最小对应的那个点你完全可以手动枚举一遍看代码输出是否一致。第二板斧是画带环的图故意制造“共享边”的情况。比如一个三角形加一条边a、b、c 分别放在三个角上。这种图表面上看路径之间有重叠用来验证“不需要专门去重也能过”这个结论非常合适。我第一次拿这种图跑之前一直担心共享边会漏算跑完发现枚举点 x 已经天然覆盖了所有可能才彻底放心。第三板斧是极限数据造法n200000m199999k200000一条链状图然后看看程序会不会爆栈或者超时。只要 BFS 用的是队列不是递归 DFS就不会爆栈。这条主要是检查代码效率一般一次就能过。6.3 从这题带走的通用套路这题做完之后我最大的收获不只是会了一个题而是对一类题目有了感觉当你碰到“给你一组权值自由分配问最短路最小值”这种问题时核心思路永远是把权值分配问题转化为“路径上需要多少条边”的问题。只要路径的边数定了权值分配就是排序贪心没有第二个可能性。这背后其实是一个很重要的建模思维权值分配的自由度应该被你利用来简化问题而不是让你去枚举所有分配方案。另外一个附带收获是“多源 BFS 枚举中点”的套路。以后遇到类似的“必经点路径最短”问题比如“从 a 到 b 再到 c 再到 d 的路径”三点版本第一反应就应该是分别从每个关键点跑 BFS然后枚举分界点组合。这个方法扩展性很强我记得后来做一道“a 经过 b 经过 c 到 d”的题目就是顺着这个套路套出来的。最后再分享一个实操小技巧如果这道题你想在脑子里彻底“立住”建议自己动手写一组三四个点的极简数据把三段最短路在图上用不同颜色标出来然后对着枚举的 x 一个个看。这个过程大概花十几分钟但比刷十道同类型题都管用。这个题在我做过的所有 Div.3 题里属于“代码量小但思维量足”的典型代表很值得反复品味。
