REALHW168 帕秋莉的魔导传输网

解题思路

经典全源最短路径问题，用 Floyd-Warshall 算法。

题目特点：

• 多组查询（最多 10^4 次），需要预处理所有点对之间的最短路径
• 同一对节点间可能有多条边，取最小权重
• 不连通输出 0

Floyd 算法的核心：枚举中转点 k，尝试用 i → k → j 更新 i → j 的最短距离。三重循环处理完后，adj[i][j] 就是任意两点间的最短路径。

代码实现

n, m = map(int, input().split())
INF = float('inf')
adj = [[INF] * n for _ in range(n)]

for i in range(n):
    adj[i][i] = 0

for _ in range(m):
    u, v, c = map(int, input().split())
    adj[u][v] = min(adj[u][v], c)
    adj[v][u] = min(adj[v][u], c)

for k in range(n):
    for i in range(n):
        for j in range(n):
            adj[i][j] = min(adj[i][j], adj[i][k] + adj[k][j])

k = int(input())
for _ in range(k):
    a, b = map(int, input().split())
    print(adj[a][b] if adj[a][b] != INF else 0)

代码解析

以示例为例，初始邻接矩阵（INF 用 ∞ 表示）：

     0    1    2    3    4
0  [ 0,  10,  ∞,   ∞,  ∞ ]
1  [ 10,  0,  20,  ∞,  ∞ ]
2  [ ∞,  20,  0,   ∞,  ∞ ]
3  [ ∞,  ∞,   ∞,   0, 40 ]
4  [ ∞,  ∞,   ∞,  40,  0 ]

Floyd 执行后，adj[0][2] = 30（经过节点 1 中转），adj[0][3] 仍为 INF（不连通）。

三处关键细节：

• 邻接矩阵初始化：对角线为 0，其余为 INF
• 重边取最小：adj[u][v] = min(adj[u][v], c)
• 查询判断：仍为 INF 说明不连通，输出 0

复杂度分析

• 时间复杂度：O(n³) 预处理 + O(1) 每次查询，n ≤ 100 完全可行
• 空间复杂度：O(n²) 存邻接矩阵