Editorial for Pondo Shortest Paths

Remember to use this editorial only when stuck, and not to 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$ ~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$ ~n \times n~ distance matrix, initialized to the direct edge weights (taking the minimum on parallel edges), with zeros on the diagonal and $\infty$ ~\infty~ elsewhere. Then, for each intermediate vertex $k$ ~k~, and every pair $(i, j)$ ~(i, j)~, relax

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

After processing every $k$ ~k~, $dist[i][j]$ ~dist[i][j]~ is the shortest-path distance from $i$ ~i~ to $j$ ~j~.

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

Solution (Python)

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()

Comments

There are no comments at the moment.