算法常见题型之最短路进阶：多源最短路

算法常见题型之最短路进阶：多源最短路

例题：https://ac.nowcoder.com/acm/contest/132303/H

一、题目大意提炼

给定一张包含nnn个点、mmm条边的无向正权连通图，以及kkk个指定的关键点。要求从这kkk个关键点中选出两个不同的点作为起点和终点，求所有可选路径中的最小花费（即关键点两两之间最短路径长度的最小值）。

二、基础回顾：单源最短路 Dijkstra 模板

适用场景与复杂度

Dijkstra 算法用于求解正权图中单一起点到所有节点的最短路径，堆优化版本的时间复杂度为 O(mlogn)，是处理十万级规模图论问题的标准算法。

核心思路

1. 初始化距离数组dist为无穷大，起点距离设为 0；
2. 使用小顶堆（优先队列）维护「当前距离 + 节点编号」，每次取出距离最小的节点；
3. 若该节点已确定最短路则跳过，否则标记为已确定，并用该节点松弛所有邻接边；
4. 重复直到队列为空。

标准模板代码

#include<bits/stdc++.h>#definepiipair<int,int>#defineintlonglongusingnamespacestd;constintN=1e5+9,inf=1e18;vector<vector<pii>>g;// 邻接表：g[u] 存储 {邻接点v, 边权w}vector<int>dist;vector<bool>st;voiddijkstra(ints,intn){dist.assign(n+1,inf);// 初始化st.assign(n+1,false);// 初始化priority_queue<pii,vector<pii>,greater<pii>>q;// 小顶堆dist[s]=0;q.push({0,s});while(!q.empty()){auto[d,u]=q.top();q.pop();if(st[u])continue;st[u]=true;for(auto[v,w]:g[u]){if(dist[v]>d+w){dist[v]=d+w;q.push({dist[v],v});}}}}

三、常规多源最短路：虚拟源点法

问题定义

多源最短路：给定多个源点，求每个节点到距离它最近的源点的最短路径长度。

经典解法

构造一个虚拟源点 S，从 S 向每一个源点连接一条权值为 0 的边。此时问题转化为求 S 到所有点的单源最短路：

仅需跑一次 Dijkstra 即可得到所有点到最近源点的距离；
时间复杂度仍为 O(mlogn)，与单次单源最短路一致。

局限性

虚拟源点法只能得到「每个点到最近源点的距离」，但无法直接求出「任意两个源点之间最短路的最小值」——这正是本题的核心求解目标。

四、本题核心解法：多源扩展 + 跨源边统计

核心结论

对于任意两个不同的源点sss和ttt，它们的最短路径上必然存在至少一条边(u,v,w)(u, v, w)(u,v,w)，满足：

uuu的最近源点是sss
vvv的最近源点是ttt

此时sss到ttt的最短路径长度等于：d[u] + w + d[v]
其中d[u]是uuu到最近源点的距离，d[v]是vvv到最近源点的距离。

因此，所有源点对之间的最短路径的最小值，就等于所有满足“两端点归属源点不同”的边对应的d[u]+w+d[v]的最小值。

算法步骤

1. 初始化：距离数组d设为无穷大，归属源点数组src设为 -1（表示无归属）；
2. 多源入队：将所有kkk个关键点加入优先队列，设置d[x] = 0，src[x] = x（自身为自身的源点）；
3. Dijkstra 扩展：按标准 Dijkstra 流程扩展节点，同时维护每个节点的归属源点；
4. 更新答案：在遍历邻边时，若边的两个端点都有归属源点且归属不同，则用d[u] + w + d[v]更新全局最小值；
5. 输出结果：最终全局最小值即为答案。

五、正解代码

#include<bits/stdc++.h>#definepiipair<int,int>#defineintlonglong// 开long long防止路径长度爆intusingnamespacestd;constintN=1e5+9,inf=1e18;intt,n,m,k,ans,x;signedmain(){cin>>t;while(t--){cin>>n>>m;vector<vector<pii>>g(n+1);while(m--){inta,b,c;cin>>a>>b>>c;g[a].push_back({b,c});g[b].push_back({a,c});// 无向边，双向加边}cin>>k;priority_queue<pii,vector<pii>,greater<>>q;// 小顶堆vector<int>src(n+1,-1),d(n+1,inf);// 初始化vector<bool>st(n+1);ans=inf+9;for(inti=0;i<k;i++){cin>>x;d[x]=0;// 源点到自身距离为0src[x]=x;// 源点的归属是自己q.push({0,x});// 所有源点同时入队}while(q.size()){auto[dd,id]=q.top();q.pop();if(st[id])continue;st[id]=1;// 标记该节点最短路已确定for(auto[j,w]:g[id]){// 跨源边：两端归属源点不同，更新答案if(src[j]!=-1&&src[id]!=-1&&src[j]!=src[id])ans=min(ans,w+d[id]+d[j]);// 标准松弛操作if(d[j]>d[id]+w){src[j]=src[id];// 继承归属源点d[j]=d[id]+w;q.push({d[j],j});}}}cout<<ans<<'\n';}return0;}

六、样例模拟

以题目样例为例：

关键点：1、3、5
边：1-2(1), 2-3(3), 3-1(3), 2-5(1), 2-4(2), 4-3(1)

1. 初始：d[1]=d[3]=d[5]=0，分别入队；
2. 弹出距离0的节点5，扩展邻接点2：d[2]更新为1，src[2]=5，入队；
3. 弹出距离0的节点1，扩展邻接点2：此时src[1]=1，src[2]=5，两者不同，计算0 + 1 + 1 = 2，ans更新为 2；
4. 后续扩展其他节点，不会得到比 2 更小的跨源路径；
5. 最终答案为 2，与样例输出一致。

七、时间复杂度验证

时间复杂度无论是单源还是多源，总时间复杂度均为 O(mlogn)，完全可以通过 n,m=1e5 的数据规模。