神 trick 之如何求5e5全源最短路
2026-08-08 11:37:25
发布于：浙江
UPD on 8/8：添加了代码。
题目：给定一张 个点 条边的无向连通图，每条边有一个边权，定义 为 的最短路。
给出 个关键点，对 个点建一个新图，其中对于每对 连一条权值为 的边。求新图 MST。
。
我怎么现在才知道这个 trick。模拟赛丢大分。
显然不能直接求出 个边，考虑优化。
将 个点一起加入，跑 Dijkstra。对于每个源点分别一种颜色，给它经过的点染色。
比如说这张图，黑点为关键点：
跑最短路后的图：
感性理解一下，这个染色相当于一个类似圆的领域。
注意到一个可能的 MST 边在原路径上不可能经过超过两个颜色。
证明：
假设存在一条边先后经过了 颜色的点，且生成树中 连有一条边。
显然此时 。
我们断开 ，然后以 为一端连向 或 ，显然会形成一棵新生成树，而边权和更小。
所以，我们枚举每条边，判断它两端点的颜色是否不同，如果不同，将它们俩颜色所在关键点连一条边即可。
当然，假设边的两端是 ，颜色是 ，长度是 ，加入跑 MST 的边权就是 ，这个在跑 Dijkstra 的时候已经算好了。
这样，我们就把边数降到了 。
跑一次 Dijkstra 是 ，连边跑 Kruskal 求 MST 也是 ，所以总复杂度为 。
模拟赛出的题，正式点，代码给全了。
#include <bits/stdc++.h>
#include <assert.h>
namespace cjdst{
typedef long long ll;
typedef std::pair <int, int> pii;
typedef std::pair <ll, ll> pll;
void init(){
std::ios::sync_with_stdio(0);
std::cin.tie(0);
std::cout.tie(0);
}
const int N = 500000;
int a[N + 5];
std::vector <pll> v[N + 5];
std::priority_queue <pll, std::vector <pll>, std::greater <pll>> q;
int color[N + 5];
ll dis[N + 5];
bool vis[N + 5];
int father[N + 5], siz[N + 5];
int find(int n){
return (father[n] == n ? n : father[n] = find(father[n]));
}
bool merge(int x, int y){
x = find(x), y = find(y);
if(x == y) return 0;
if(siz[x] > siz[y]) std::swap(x, y);
father[x] = y, siz[y] += siz[x];
return 1;
}
int n, m, k;
void solve(){
std::cin >> n >> m >> k;
for(int i = 1; i <= k; i++){
std::cin >> a[i];
}
for(int i = 1; i <= m; i++){
int x, y, z;
std::cin >> x >> y >> z;
v[x].push_back({y, z});
v[y].push_back({x, z});
}
memset(dis, 63, sizeof(dis));
for(int i = 1; i <= k; i++){
dis[a[i]] = 0;
q.push({0, a[i]});
color[a[i]] = i;
}
while(!q.empty()){// Dijkstra
auto head = q.top();
q.pop();
if(vis[head.second]) continue;
vis[head.second] = 1;
for(auto it:v[head.second]){
if(dis[it.first] > dis[head.second] + it.second){
dis[it.first] = dis[head.second] + it.second;
color[it.first] = color[head.second];
q.push({dis[it.first], it.first});
}
}
}
struct node{
ll x, y, z;
bool operator < (const node &b) const{
return z < b.z;
}
};
std::vector <node> edges;
for(int i = 1; i <= n; i++){// 建边
for(auto j:v[i]){
if(color[i] != color[j.first]){
edges.push_back({color[i], color[j.first], dis[i] + dis[j.first] + j.second});
}
}
}
std::sort(edges.begin(), edges.end());
for(int i = 1; i <= k; i++){
father[i] = i;
siz[i] = 1;
}
ll ans = 0;
for(auto it:edges){// kruskal
if(merge(it.x, it.y)) ans += it.z;
}
std::cout << ans << '\n';
}
}
int main(){
cjdst::init();
int T = 1;
// std::cin >> T;
for(int _ = 1; _ <= T; _++){
cjdst::solve();
}
}
全部评论 11
春风使时光微微萌动。时光在春意中飘散，俯视着努力仰望的我们。
在仰望什么呢？
是在仰望世界吗？世界的繁华聚焦于瞳孔之中，却像是散瞳了。看清了世界，却唯独模糊了自己。真爱的目光从这里逐渐变为过客的匆匆一瞥。
是在仰望神明吗？愚钝的人徘徊着，坠于嫉妒之谷，陷于拖沓之潭，铮铮地望着。聪慧的人踏出了脚步，却不知道自己挡住了多少人仰望的目光，堵住了多少人追赶的步伐。
是在仰望欲望吗？木偶的提线，似乎如何仰望都看不见操纵的手，只知道一根根线融入一个个数一行行字中，一次松动喜悦着心，一次收紧压迫了魂。只不过是虚无缥缈的，随着风无助地飘飘摇摇，一挥手，就在风中破碎，微弱的反光会逐渐消散，仿佛从未来过。
难道，是在仰望过去？
我伸出手，从房间的角落轻轻捧起一小缕时光，晶莹的光若隐若现。它在孤寂之处默默沉淀光彩，留存住岁月的足迹。在注视之下，它不停地扩展开来，张开一片片羽翼，直到占据了整个目光。它投映出一个个人。是你。是你们。是那个纯真的我。我轻轻张开指尖，一小滴时光滴落，这台建造在我手上的精妙机器渐渐塌陷，坠落，凝聚成我无法看见的一小片。
是岁月。我明白了。岁月的影子。
在太阳升起时，影子会默默出现。在意识沉睡时，影子为世人以刻下最美的碑痕。在太阳落下时，万物皆沉，唯有影子向上攀登。影子在黑暗中抚慰每一个迷路的人。
我想起了你。
不不要离去不要抛下我和回忆不要留下一个迷宫中徘徊的欲望与对比的提线木偶不要让我一个人在黑夜中缓缓回味不要留下我一个人追求 OI 之梦……
原来你也成为了我的影子，是吗？
当太阳的光辉普照大地时，只有影子能承担随之而来的黑暗。
我将手从角落收回，贴在胸前。
上帝知道，我愿意替你离去。
当我从朝圣之路坠入深渊，让我们一起刻下岁月的碑痕。
让我们一起仰望永恒的时光。
让我们一起变成影子吧。
1周前 来自 浙江
0这不禁让我想起了《安德的影子》 是美国作家奥森·斯科特·卡德创作的科幻小说，英文原版《Ender's Shadow》于2000年由Tor Books首次出版，中文翻译版《安德的影子》由郭卫文翻译、浙江文艺出版社于2016年6月出版，属于“典藏版” 。该书作为《安德的游戏》系列的平行作品，是“影子系列”的首部作品 。作者奥森·斯科特·卡德是美国科幻作家，其作品《安德的游戏》（Ender’s Game）曾获得雨果奖和星云奖。《安德的影子》是一本平行小说，从另一侧面叙述了人类与虫族决战的事件。该书以《安德的游戏》系列中的配角“豆子”（朱里安·戴尔菲科）为第一人称视角，讲述了同一事件之下的另一角度的故事。
1周前 来自 广东
0
有帮助，赞一个