Editorial for Pondo Shortest 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, connected, and has non-negative edge weights, with $n \le 100$ . The task is to compute all-pairs shortest-path distances.

Floyd–Warshall is a natural fit. Store a dense $n \times n$ distance matrix, initialized to the direct edge weights (taking the minimum on parallel edges), with zeros on the diagonal and $\infty$ elsewhere. Then, for each intermediate vertex $k$ , and every pair $(i, j)$ , relax

$dist[i][j] = \min(dist[i][j], dist[i][k] + dist[k][j])$ .

After processing every $k$ , $dist[i][j]$ is the shortest-path distance from $i$ to $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]
    dist = [[INF] * n for _ in range(n)]
    for i in range(n):
        dist[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 < dist[u][v]:
            dist[u][v] = w
            dist[v][u] = w

    for k in range(n):
        dk = dist[k]
        for i in range(n):
            dik = dist[i][k]
            if dik == INF:
                continue
            di = dist[i]
            for j in range(n):
                cand = dik + dk[j]
                if cand < di[j]:
                    di[j] = cand

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


if __name__ == "__main__":
    main()

Comments0

No comments yet

Be the first to comment.

Editorial for Pondo Shortest Paths

Approach

Solution (Python)

Comments0

New comment