Floyd 后枚举传送门端点，逐点对比较原路和两个传送方向。
OJ: luogu
题目 ID: P6464
难度:普及+/提高-
标签:Floyd枚举全源最短路python
创建: 2026-07-17 03:00
更新: 2026-10-20 15:32
题意
选择两个点安装距离为 0 的双向传送门，最小化所有无序点对最短路之和。
思路
传送门等价于在 a、b 之间加一条权为 0 的双向边。最直接的做法是枚举 C(n,2) 个端点对，每次加边后重跑 Floyd，复杂度 O(n^5)。
这个算法不需要：因为只有一条边被改动，重算的 99% 是重复的。
为什么不必重跑 Floyd
一条新最短路只有两种形态，分开看就能直接写出答案：
不走传送门。 原图的边全在，旧路径依然可用，所以最短路不会变长，距离仍是原矩阵里的 d[x][y]。这一支不需要任何计算，这就是最优子结构在起作用：子问题的最优值在「不使用新边」的前提下保持不变，整张表可以复用。
走传送门。 这时传送门用几次才是真正的卡点。
零权让「多次使用」退化成「一次」
如果一条路径两次经过传送门，比如 ... → a → b → ... → a → b → ...，那么中间那段「从 b 回到 a」的行程可以整段删掉，长度不会增加——因为传送门本身的代价是 0。所以任何用到传送门的路径都可以化简成只用一次。
这一条是有前提的：新边权必须非负。本题传送门权为 0，所以重复使用无收益。换成「传送一次要花 c」且 c ≥ 0 仍成立；若 c < 0，绕环可以用越多次越短，路径会无限变短，「至多用一次」直接失效。
传送门是双向的，所以「用一次」有两个方向：
三个候选对应三种互斥情形，取最小即得新距离。每对 (x,y) 只花 O(1)，不必重跑 Floyd。
单条边才能一次松弛到底
上面的公式只做了一轮 min。这足够，是因为只加一条边：新边权为 0、且不产生新的中间点，因此不存在「先用新边、再回头用新边」这种需要多轮迭代的依赖。若同时加入一整批新边，或多对端点各自加边且互相影响，单轮 min 就盖不全了，必须重新跑 Floyd。
三个层次缺一不可
| 层次 | 内容 | 作用 |
|---|---|---|
| 最优子结构 | 不用新边的路径长度仍等于原 d[x][y] |
d 表可直接复用 |
| 零权退化 | 权为 0 时多次使用可化简为一次 | 候选只有 2 个方向 |
| 单边增量 | 只加一条边，一轮松弛即到不动点 | O(1) 公式可代替重跑 |
前两层让你能把答案写成三个候选，第三层让你不用迭代。少了任何一条，这个 O(n^4) 的写法就不成立。
边界：点对 (a,b) 本身也要算
传送门建成后 d'[a][b] = 0，而 (a,b) 也是总和中一项（样例里“1 → 4 的最短路是 0”就计入了总和）。只枚举 a < b 且求和时用 x < y，(a,b) 自然会被包含；但如果为了避开退化情形而把 a、b 从点对枚举里排除，就会少算这一项，答案偏大。
Python 知识
- 二维列表直接保存百点规模距离矩阵。
- 内层缓存行引用减少多重索引：
row = distance[x]之后只做一次二维访问。 min接收三个候选，和上面的公式一一对应。- 枚举端点时只取
second > first，点对只取y > x，用对称性把枚举量减半。
代码
#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-07-17 01:40
# update_at: 2026-10-20 15:32
#
# main.py：传送门。只能装一对、把两栋楼之间距离变成 0，求安装后所有无序点对最短路之和的最小值。
# 全源最短路部分沿用 rbook 代码模板 floyed-py（《Floyd-Warshall 全源最短路》）：
# 点编号 1..n，floyd(n, edges) 返回 (n+1) 阶矩阵，INF 表示不可达，平行边只保留最小权值。
#
# 传送门等价于在 a、b 之间加一条权为 0 的双向边。不必为每个候选重跑 Floyd：
# 不用这条新边：原图边全在，距离仍是原矩阵的 d[x][y]（最优子结构，d 表直接复用）；
# 用这条新边：权为 0，所以多次经过可化简成一次，且传送门双向，只有两个方向。
# 于是新距离就是三个候选取最小：
# d'[x][y] = min(d[x][y], d[x][a] + d[b][y], d[x][b] + d[a][y])
# 每对 (x,y) 只花 O(1)，整体 O(n^3) 一次 Floyd + O(n^4) 枚举。
# 注意：(a,b) 这一对本身也要计入总和，装传送门后它是 0。
import sys
INF = 1 << 60 # 哨兵，约 1.15e18，比任何合法路径都大
type Grid = list[list[int]]
def floyd(n: int, edges: list[tuple[int, int, int]]) -> Grid:
"""返回 n+1 阶距离矩阵；dist[0][*] 与 dist[*][0] 恒为 INF，不使用。"""
dist: Grid = [[INF] * (n + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
dist[i][i] = 0 # 自己到自己距离 0
for u, v, w in edges:
if w < dist[u][v]: # 平行边保留最小权值
dist[u][v] = w
for k in range(1, n + 1):
for i in range(1, n + 1):
if dist[i][k] == INF:
continue # i 到中转点 k 不可达，松弛无意义
for j in range(1, n + 1):
if dist[k][j] == INF:
continue
nd = dist[i][k] + dist[k][j]
if nd < dist[i][j]:
dist[i][j] = nd
return dist
def solve() -> None:
data = iter(map(int, sys.stdin.buffer.read().split()))
n, m = next(data), next(data)
edges: list[tuple[int, int, int]] = []
for _ in range(m):
u, v, w = next(data), next(data), next(data)
# 无向边两个方向都要建；模板里按有向边处理，所以这里各加一次
edges.append((u, v, w))
edges.append((v, u, w))
dist = floyd(n, edges) # dist[i][j]：原图中 i 到 j 的最短路
answer = INF
for first in range(1, n + 1):
for second in range(first + 1, n + 1):
from_second = dist[second]
from_first = dist[first]
total = 0
for x in range(1, n + 1):
row = dist[x] # 缓存行引用，内层只做一次二维访问
left = row[first] # d[x][a]，内层循环里不变
right = row[second] # d[x][b]，同理
for y in range(x + 1, n + 1):
# 不用传送门 / 经 a->b / 经 b->a，三者取最小
total += min(row[y], left + from_second[y], right + from_first[y])
if total < answer:
answer = total
print(answer)
if __name__ == "__main__":
solve()原有 C++ 版本仍保留：
/**
* Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
* rbook: -> https://rbook.roj.ac.cn https://rbook2.roj.ac.cn
* rainboy的学习导航网站: https://idx.roj.ac.cn
* create_at: 2026-07-17 01:40
* update_at: 2026-10-20 14:55
*/
// 传送门：只能装一对、把两栋楼之间距离变成 0，求安装后所有无序点对最短路之和的最小值。
// 传送门等价于在 a、b 之间加一条权为 0 的双向边。不必为每个候选重跑 Floyd：
// 不用这条新边：原图边全在，距离仍是原矩阵的 d[x][y]（最优子结构，d 表直接复用）；
// 用这条新边：权为 0，所以多次经过可化简成一次，且传送门双向，只有两个方向。
// 于是新距离就是三个候选取最小：
// d'[x][y] = min(d[x][y], d[x][a] + d[b][y], d[x][b] + d[a][y])
// 每对 (x,y) 只花 O(1)，整体 O(n^3) 一次 Floyd + O(n^4) 枚举。
// 注意：(a,b) 这一对本身也要计入总和，装传送门后它是 0。
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 105; // 点数上界 n <= 100
const long long INF = (1LL << 60);
int n, m;
long long dist_node[MAXN][MAXN]; // 原图任意两点最短路；dist_node[i][i] = 0
void floyd() {
for (int middle = 1; middle <= n; middle++) {
for (int start = 1; start <= n; start++) {
// 若 start 到 middle 都不可达，后面整轮都不用试
if (dist_node[start][middle] == INF) continue;
long long base = dist_node[start][middle];
for (int finish = 1; finish <= n; finish++) {
long long candidate = base + dist_node[middle][finish];
if (candidate < dist_node[start][finish]) {
dist_node[start][finish] = candidate;
}
}
}
}
}
void read_input() {
cin >> n >> m;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
dist_node[i][j] = (i == j) ? 0 : INF;
}
}
for (int i = 1; i <= m; i++) {
int u, v;
long long w;
cin >> u >> v >> w;
// 题面保证无重边无自环，直接赋值即可
dist_node[u][v] = w;
dist_node[v][u] = w;
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
read_input();
floyd();
long long answer = INF;
for (int first = 1; first <= n; first++) {
for (int second = first + 1; second <= n; second++) {
long long total = 0;
for (int x = 1; x <= n; x++) {
for (int y = x + 1; y <= n; y++) {
// 不用传送门 / 经 first->second / 经 second->first，三者取最小
long long best = dist_node[x][y];
long long through_first = dist_node[x][first] + dist_node[second][y];
long long through_second = dist_node[x][second] + dist_node[first][y];
if (through_first < best) best = through_first;
if (through_second < best) best = through_second;
total += best;
}
}
if (total < answer) answer = total;
}
}
cout << answer << '\n';
return 0;
}复杂度
一次 Floyd 是 O(n^3)，枚举端点是 C(n,2) ≈ n^2/2，每个端点对枚举点对又是 C(n,2)，合计约 2C(n,2)^2 ≈ n^4/2。
n = 100 时约 2.5 × 10^7 次 min 运算：C++ 轻松通过，Python 约 10 秒（本题无严格时限压力）。如果不能用“至多用一次”把重跑 Floyd 省掉，那才是 O(n^5) = 10^10，绝无可能通过。
总结
加一条权为 0 的边后，新最短路要么不用它、要么只用一次：不用时距离不变（最优子结构复用原表），用时只有两个方向。零权是“至多用一次”的前提，单条边是“一轮松弛即可”的前提，三条合起来才把 O(n^5) 降到 O(n^4)。
