[传智杯 #2 决赛] 传送门

题意

选择两个点安装距离为 0 的双向传送门，最小化所有无序点对最短路之和。

思路

先 Floyd 得到原图任意两点距离。固定传送门 a,b 后，点对 x,y 的新距离是原距离、x-a-b-y、x-b-a-y 三者最小值；枚举端点和点对求总和。

Python 知识

二维列表直接保存百点规模距离矩阵。
内层缓存行引用减少多重索引。
min 接收三个候选，和公式一一对应。

代码

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34import sys


input = sys.stdin.buffer.readline
n, edges = map(int, input().split())
infinity = 10**18
distance = [[infinity] * n for _ in range(n)]
for node in range(n):
    distance[node][node] = 0
for _ in range(edges):
    u, v, weight = map(int, input().split())
    u -= 1
    v -= 1
    distance[u][v] = distance[v][u] = weight
for middle in range(n):
    through = distance[middle]
    for start in range(n):
        row = distance[start]
        base = row[middle]
        for end in range(n):
            row[end] = min(row[end], base + through[end])

answer = infinity
for first in range(n):
    from_first = distance[first]
    for second in range(first + 1, n):
        from_second = distance[second]
        total = 0
        for x in range(n):
            row = distance[x]
            for y in range(x + 1, n):
                total += min(row[y], row[first] + from_second[y], row[second] + from_first[y])
        answer = min(answer, total)
print(answer)

原有 C++ 版本仍保留：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16/**
 * 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-07-17 01:40
 */
#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    return 0;
}

复杂度

Floyd O(n^3)，枚举约 O(n^4)，但 n<=100，实际约四分之一点对组合。

总结

加一条特殊边后，任意新最短路至多使用一次这条边，可直接枚举两个方向。

[传智杯 #2 决赛] 传送门

目录

题意

思路

Python 知识

代码

复杂度

总结