Editorial for Bottleneck Paths

Use this editorial only when stuck, and do not copy-paste code from it.

Please be respectful to the problem author and editorialist. Submitting an official solution before solving the problem yourself is a bannable offence.

Approach

The graph is undirected and connected with $n \le 100$ , so an $O(n^3)$ all-pairs algorithm is acceptable.

This is the same shape as Floyd–Warshall, except the path cost is the maximum edge weight on the path, and we want to minimize that cost. Initialize a dense matrix with direct edge weights (taking the minimum on parallel edges), zeros on the diagonal, and $\infty$ elsewhere. Then, for each intermediate vertex $k$ and every pair $(i, j)$ , relax

$best[i][j] = \min\bigl(best[i][j],\ \max(best[i][k], best[k][j])\bigr)$ .

After every $k$ is processed, $best[i][j]$ is the minimum achievable bottleneck between $i$ and $j$ .

The time complexity is $O(n^3)$ .

Solution (Python)

Code 1

import sys

INF = 10**18


def main() -> None:
    data = list(map(int, sys.stdin.buffer.read().split()))
    n, m = data[0], data[1]
    best = [[INF] * n for _ in range(n)]
    for i in range(n):
        best[i][i] = 0

    idx = 2
    for _ in range(m):
        u = data[idx] - 1
        v = data[idx + 1] - 1
        w = data[idx + 2]
        idx += 3
        if w < best[u][v]:
            best[u][v] = w
            best[v][u] = w

    for k in range(n):
        bk = best[k]
        for i in range(n):
            bik = best[i][k]
            if bik == INF:
                continue
            bi = best[i]
            for j in range(n):
                bkj = bk[j]
                if bkj == INF:
                    continue
                cand = bik if bik >= bkj else bkj
                if cand < bi[j]:
                    bi[j] = cand

    out_lines = [" ".join(map(str, row)) for row in best]
    sys.stdout.write("\n".join(out_lines) + "\n")


if __name__ == "__main__":
    main()

Comments0

No comments yet

Be the first to comment.

Editorial for Bottleneck Paths

Approach

Solution (Python)

Comments0

New comment