Dijkstra Shortest Distances

core

You are given a directed, weighted graph on nodes 0 through n-1 as a weighted adjacency list adj, where adj[u] lists (v, w) pairs: an edge from u to v with positive weight w (the same shape you built in Build a Weighted Adjacency List). Complete dijkstra_dist(n, adj, src) so it returns the minimum total edge weight from src to every node, with -1 for any node not reachable from src. The heap push/pop plumbing and the relaxation loop are already written; you fill in the two lines interviews actually test. First, the distance array: every node starts at INF (a sentinel no real path can reach) and only dist[src] starts at 0; initialize anything to 0 and every node looks already reached. Second, the stale-entry skip: this Dijkstra never deletes an outdated heap entry when a node's distance improves, it just pushes a new cheaper one, so when you pop (d, u) and d is worse than the recorded dist[u], that entry is stale and you must continue past it without relaxing. Do not fall back on the BFS habit of finalizing a node the moment it is first pushed: with weighted edges, the first push is not necessarily the shortest path.

Example: dijkstra_dist(3, {{(1,10), (2,1)}, {}, {(1,1)}}, 0) returns {0, 2, 1}. Node 1 is first pushed at distance 10, then improved to 2 via node 2; when the old (10, 1) entry is finally popped, 10 > dist[1] == 2, so it is skipped as stale.

Input format: each test in tests/*.in is laid out as:

Line 1: n e, the node count and the number of directed edges; nodes are numbered 0 to n - 1.
Next e lines: u v w, one directed edge from u to v with weight w.
Last line: s, the start node passed to dijkstra_dist.

Test 02.in reads:

This is 4 nodes and 3 edges, starting from node 0. The first edge 0 0 5 is a weighted self-loop, and node 2 has no incoming edge, so it stays unreachable.

Where you'll use it:

✦ Solution & editorial unlock with the pass.