P6464 [传智杯 #2 决赛] 传送门（绿色普及+/提高）

graph, 最短路, Floyd算法, https://www.luogu.com.cn/problem/P6464

传智专修学院里有 $n$ 栋教学楼，有 $m$ 条双向通行道路连接这些教学楼，不存在重边和自环。每条道路都有一定的长度，而且所有教学楼之间都可以直接或者间接的通过道路到达。我们可以很容易的求出这些教学楼之间的最短路。

为了使交通更为顺畅，校方决定在两个教学楼里增设一对传送门。传送门可以将这对教学楼的距离直接缩短为 0。利用传送门，某些教学楼之间的最短路的距离就变短了。

由于预算有限，学校里只能安装一对传送门。但是校长希望尽可能方便学生，使任意两点之间的最短路长度的总和最小。当然啦，从 $x$ 教学楼到 $y$ 教学楼的长度和从 $y$ 教学楼到 $x$ 教学楼的长度只需要统计一次就可以了。

输入格式

输入第 1 行两个正整数 $n, m (n \leq 100, m \leq \frac{1}{2} n (n - 1))$ ，代表教学楼和道路数量。

接下来 $m$ 行，每行三个正整数 $x_{i}, y_{i}, w_{i} (0 < w_{i} \leq 10^{4})$ ，表示在教学楼 $x_{i}$ 和 $y_{i}$ 之间，有一条长度为 $w_{i}$ 的道路。

输出格式

输出一行，在最优方案下的任意点对的最短道路之和。

输入输出样例 #1

输入 #1

输出 #1

说明/提示

样例如图。当在 1 和 4 号教学楼架设一对传送门时，1 → 2 的最短路是 3，1 → 3 的最短路是 0+2，1 → 4 的最短路是 0，2 → 3 的最短路是 4，2 → 4 的最短路是 3+0，3 → 4 的最短路是 2，最短路之和是 14，是最佳方案。

下面是本题的 0-indexed 双重循环优化及 Floyd-Warshall 算法的 Python 实现。

解题思路

多源最短路计算：由于 $N \leq 100$ ，可以先使用 Floyd-Warshall 算法求出任意两点之间的初始最短距离，时间复杂度为 $O (N^{3})$ 。
枚举传送门位置：一共有 $\frac{N (N - 1)}{2}$ 种不同的传送门放置方案。可以枚举这一对传送门所在的教学楼 $(u, v)$ 。
计算新的最短路之和：假设在 $u$ 和 $v$ 之间设立了传送门，则它们之间的距离变为了 $0$ 。对于任意两个点 $i$ 和 $j$ ，它们之间新的最短距离 $d^{'} (i, j)$ 只有以下三种可能：
- 不通过传送门：距离为 $d (i, j)$ 。
- 通过传送门（从 $u$ 到 $v$ ）：距离为 $d (i, u) + 0 + d (v, j) = d (i, u) + d (v, j)$ 。
- 通过传送门（从 $v$ 到 $u$ ）：距离为 $d (i, v) + 0 + d (u, j) = d (i, v) + d (u, j)$ 。
因此，新的最短距离为：
$d^{'} (i, j) = min (d (i, j), d (i, u) + d (v, j), d (i, v) + d (u, j))$
通过遍历所有的点对 $(i, j)$ 算出它们的新的最短路径之和。由于 $N \leq 100$ ，整体计算量约为 $\frac{N (N - 1)}{2} \times \frac{N (N - 1)}{2} \approx 2.5 \times 10^{7}$ 次操作。在 Python 中，通过局部变量缓存和底层的比较优化，可以保证程序高效运行。

Python 3 实现

python

import sys

def solve():
    # 快速读入所有数据
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    n = int(input_data[0])
    m = int(input_data[1])
    
    # 初始化二维数组 d，d[i][j] 表示点 i 到点 j 的最短距离
    INF = 10**9
    d = [[INF] * n for _ in range(n)]
    
    # 每个点到它本身的距离为 0
    for i in range(n):
        d[i][i] = 0
        
    # 读取输入的边并更新图的邻接矩阵（考虑可能有重边，取较小值）
    idx = 2
    for _ in range(m):
        u = int(input_data[idx]) - 1
        v = int(input_data[idx+1]) - 1
        w = int(input_data[idx+2])
        idx += 3
        if w < d[u][v]:
            d[u][v] = w
            d[v][u] = w
            
    # 标准 Floyd-Warshall 算法计算任意两点间的最短路径
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if d[i][k] + d[k][j] < d[i][j]:
                    d[i][j] = d[i][k] + d[k][j]
                    
    ans = INF
    
    # 枚举建立传送门的两个教学楼 u 和 v (u < v)
    for u in range(n):
        for v in range(u + 1, n):
            current_sum = 0
            
            # 计算在 u 和 v 之间建立传送门后，所有教学楼对之间的最短距离之和
            for i in range(n):
                for j in range(i + 1, n):
                    # 两点间新的最短距离只有以下三种可能：
                    # 1. 不走传送门：d[i][j]
                    # 2. 走传送门（由 u 到 v）：d[i][u] + d[v][j]
                    # 3. 走传送门（由 v 到 u）：d[i][v] + d[u][j]
                    new_dist = min(d[i][j], d[i][u] + d[v][j], d[i][v] + d[u][j])
                    current_sum += new_dist
                    
            # 记录所有方案中的最小值
            if current_sum < ans:
                ans = current_sum
                
    print(ans)

if __name__ == '__main__':
    solve()

复杂度分析

时间复杂度：
- Floyd-Warshall 算法： $O (N^{3})$ 。
- 枚举方案并求和：共有 $O (N^{2})$ 种方案，每次求和需要 $O (N^{2})$ 的时间。整体时间复杂度为 $O (N^{4})$ 。在 $N \leq 100$ 的数据规模下，最内层循环执行次数约 $2.45 \times 10^{7}$ 次，优化后的 Python 代码能在规定时间内完成评测。如果使用 PyPy 运行，效率会更高。
空间复杂度：
- $O (N^{2})$ ，用于存储任意两点间距离的二维数组。

P6464 [传智杯 #2 决赛] 传送门（绿色 普及+/提高） ​

P6464 [传智杯 #2 决赛] 传送门（绿色普及+/提高）