魔导传输网络

题目描述

帕秋莉正在红魔馆的地下图书馆构建一套魔导传输网络。该网络由 n 个编号为 0 ~ n-1 的魔导单元组成，单元之间通过 m 条双向传输通道进行信息交换。每条通道连接两个特定的单元，并有一定的传输延迟 c。同一对单元之间可能存在多条不同的通道。

咲夜需要协助帕秋莉计算特定单元对之间的最小传输总延迟。如果两个单元之间存在多条路径，找出总延迟之和最小的一条；若两个单元之间没有任何路径相连，则输出 0。

数据范围：

• 1 ≤ n ≤ 100
• 1 ≤ m ≤ n²
• 1 ≤ c ≤ 100
• 1 ≤ k ≤ 10⁴（查询次数）

示例

输入：

5 3
0 1 10
1 2 20
3 4 40
3
0 2
0 3
3 4

输出：

30
0
40

说明：

• 0→1→2 总延迟 = 10+20 = 30
• 0 与 3 不连通，输出 0
• 3↔4 直接连通，总延迟 = 40

解题思路

为什么选 Floyd？

• n ≤ 100 很小，O(n³) = 10⁶ 完全够用
• 查询次数 k ≤ 10⁴，Floyd 预处理后每次 O(1) 查表，远优于每次 Dijkstra

Floyd-Warshall 算法：

核心三重循环：

for k in 0..n-1:       // 枚举中转点
  for i in 0..n-1:     // 枚举起点
    for j in 0..n-1:   // 枚举终点
      dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

含义：尝试经过节点 k 中转，看是否能缩短 i 到 j 的距离。

初始化：

• dist[i][i] = 0
• dist[i][j] = c（直接相连的边，重边取最小）
• 其余为 Infinity

代码实现

function floyd(n, edges) {
    const INF = Infinity;
    const dist = Array.from({ length: n }, (_, i) =>
        Array.from({ length: n }, (_, j) => (i === j ? 0 : INF))
    );

    // 填入边（重边取最小）
    for (const [a, b, c] of edges) {
        if (c < dist[a][b]) {
            dist[a][b] = c;
            dist[b][a] = c; // 无向图
        }
    }

    // Floyd 核心：枚举中转点 k
    for (let k = 0; k < n; k++) {
        for (let i = 0; i < n; i++) {
            if (dist[i][k] === INF) continue; // 剪枝
            for (let j = 0; j < n; j++) {
                const through = dist[i][k] + dist[k][j];
                if (through < dist[i][j]) {
                    dist[i][j] = through;
                }
            }
        }
    }

    return dist;
}

// 主流程
function solve(n, edges, queries) {
    const dist = floyd(n, edges);
    return queries.map(([i, j]) => {
        const d = dist[i][j];
        return d === Infinity ? 0 : d;
    });
}

拓展：Dijkstra 堆优化版

如果只有少量查询，也可以用 Dijkstra 堆优化（O((n+m) log n) per query）。

function dijkstraHeap(n, graph, start) {
    const INF = Infinity;
    const dist = new Array(n).fill(INF);
    dist[start] = 0;

    const heap = [[0, start]]; // [距离, 节点]

    while (heap.length > 0) {
        const [d, u] = heapPop(heap);
        if (d > dist[u]) continue; // 懒删除

        for (let v = 0; v < n; v++) {
            if (graph[u][v] === INF) continue;
            const newDist = dist[u] + graph[u][v];
            if (newDist < dist[v]) {
                dist[v] = newDist;
                heapPush(heap, [newDist, v]);
            }
        }
    }

    return dist;
}

复杂度分析

• 时间复杂度： O(n³ + k)，Floyd 预处理 O(n³)，k 次查询每次 O(1)。
• 空间复杂度： O(n²)，存储距离矩阵。

5 3
0 1 10
1 2 20
3 4 40
3
0 2
0 3
3 4

30
0
40