Editorial for Copy Paste 3???

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

Edge weights may be negative, so Dijkstra's algorithm is not valid. Because the graph has no negative cycles and every node is reachable from node $1$ , Bellman-Ford computes the shortest paths correctly.

Initialize $dist[1] = 0$ and $dist[v] = \infty$ for every other node. Then relax every edge up to $n - 1$ times: for each edge $a \to b$ with weight $c$ , set $dist[b] = \min(dist[b], dist[a] + c)$ . After at most $n - 1$ passes, $dist[v]$ is the shortest-path distance from $1$ to $v$ .

Each pass scans all edges, so the time complexity is $O(nm)$ .

Solution (Python)

Code 1

import sys

INF = 10**30


def main() -> None:
    data = list(map(int, sys.stdin.buffer.read().split()))
    n, m = data[0], data[1]
    edges: list[tuple[int, int, int]] = []
    idx = 2
    for _ in range(m):
        fro = data[idx] - 1
        to = data[idx + 1] - 1
        weight = data[idx + 2]
        idx += 3
        edges.append((fro, to, weight))

    distances = [INF] * n
    distances[0] = 0

    for _ in range(n - 1):
        updated = False
        for fro, to, weight in edges:
            if distances[fro] == INF:
                continue
            cand = distances[fro] + weight
            if cand < distances[to]:
                distances[to] = cand
                updated = True
        if not updated:
            break

    print(" ".join(str(distances[i]) for i in range(1, n)))


if __name__ == "__main__":
    main()

Comments0

No comments yet

Be the first to comment.

Editorial for Copy Paste 3???

Approach

Solution (Python)

Comments0

New comment