← Back to problems
UNSW COMP2521 · medium

Dijkstra: Shortest Distances from 0

Dijkstra: Shortest Distances from 0

Given a non-negative weighted undirected graph, find the shortest distance from node 0 to every node; print -1 for unreachable.

Input: line 1 V E; then E lines u v w (undirected edge of weight w). Output: one line of V integers, the i-th is dist(0, i) or -1, space-separated.

Use a min-heap: pop the nearest unvisited node, relax its neighbours.