Editorial for Copy Paste 3???

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

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$ ~1~, Bellman-Ford computes the shortest paths correctly.

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

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

Solution (Python)

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

Comments

There are no comments at the moment.