Shortest Paths

Key Observation

This is a single-source shortest path problem on an undirected weighted graph. The important part is that every edge has nonnegative weight:

$$0 \le w \le 10^5$$

So Dijkstra's algorithm works. No Bellman-Ford drama, no negative-cycle horror movie, just the standard tool doing standard-tool things.

Dijkstra State

Let

$$dist[v]$$

be the shortest distance currently known from node $1$ to node $v$.

Initialize:

$$dist[1] = 0$$

and for every other node:

$$dist[v] = \infty$$

We store graph edges in an adjacency list. Since the graph is undirected, every input edge $(u,v,w)$ is inserted twice: once as $u \to v$ and once as $v \to u$.

Relaxation

When we know a candidate distance to node $u$, we try to improve all neighbors $v$ connected by an edge of weight $w$.

The transition is:

$$\text{if } dist[v] > dist[u] + w,$$

then update:

$$dist[v] = dist[u] + w.$$

This is called relaxing an edge. Fancy name, simple idea: "can I get there cheaper through here?"

Priority Queue

Dijkstra always expands the currently closest unprocessed-looking node. We use a min-priority queue containing pairs:

$$(distance, node)$$

C++'s priority_queue is max-first by default, so we use greater<> to make it a min-heap.

A node can enter the queue multiple times if we later find a better distance. When we pop a pair $(d,u)$, we check:

$$d \ne dist[u]$$

If true, that entry is outdated and we skip it. This keeps the implementation short and clean.

Output

After Dijkstra finishes, every reachable node $v$ has its shortest distance in $dist[v]$. If $dist[v]$ is still $\infty$, then node $v$ is unreachable from node $1$.

Print values for nodes:

$$2,3,\dots,n$$

one per line, replacing unreachable distances by $-1$.

Complexity

Each edge relaxation can push into the priority queue, so the complexity is:

$$O((n+m)\log n)$$

Memory usage is:

$$O(n+m)$$

With $n \le 100$, this is hilariously safe. The constraints are basically a warm blanket.