1689. Which Depot Serves Each Junction

A network has n junctions and m two-way roads with non-negative travel times. k distinct junctions hold a depot. For every junction, print WHICH depot serves it and how far away that depot is, one junction per line.

A junction is served by its nearest depot. When two depots are equally near, the one with the SMALLER JUNCTION NUMBER serves it, which is what makes the answer unique. Print -1 -1 for a junction that can reach no depot.

``` 5 junctions, depots at 1 and 5, every road taking 1 1 - 2 2 - 3 3 - 4 4 - 5

1 0 1 1 1 2 5 1 5 0 ```

Junction 3 is two roads from both depots, so depot 1 takes it.

## The four things that have to be said

directed? no. Every road may be driven either way. self-loops? allowed, and never on a shortest route. parallel roads? allowed, at different times, and the quicker copy wins. unreachable? yes, per junction: a piece with no depot prints -1 -1 throughout. When n is 1 that junction holds the depot and serves itself, printing "1 0".

## Why the tie-break is part of the problem

Problem 1686 prints distances, and a distance is a number: two correct programs agree. Here the answer names a depot, and on a tie there is nothing in the distances to choose between them, so the two programs would disagree and both be right. Pinning the smaller junction number is what makes the question answerable at all, and it is the same move problem 1663 makes for a route.

## What most people try first

The multi-source seeding of problem 1686, with the owner recorded the first time each junction is reached. That is nearly right and it gets ties wrong: which depot arrives first at an equidistant junction is decided by heap order, not by junction number.

The second instinct is to run the seeded search for the distances and then make a second pass to fix the owners. There is nothing to fix them with: by then every junction has one distance and no record of which depots achieve it.

## Make the key a pair

Seed every depot and carry the owner as a SECOND key, compared only when the distances tie:

for each depot d: key[d] = (0, d), push it pop the smallest (distance, owner) pair relaxing road (u, v, w): candidate = (key[u].dist + w, key[u].owner) if candidate < key[v] lexicographically, take it

## Why Dijkstra still works on a pair key

Dijkstra needs a total order on keys in which combining a key with an edge gives a key that is not smaller. The distance is non-decreasing because the weights are non-negative; the owner is carried along UNCHANGED by a relaxation, so a candidate is never smaller than the key it came from. Lexicographic order on the pair therefore has the property required, and the proof goes through word for word.

The owner being carried rather than recomputed is the detail that matters: a relaxation copies key[u].owner into v, so the owner of a junction is whichever depot owns the predecessor on its chosen route. That is what makes the tie-break propagate instead of being decided locally at each step.

## Overflow, computed rather than assumed

A shortest route is simple, so at most n - 1 = 49999 roads of up to 10^9 give a distance near 5 * 10^13, past the 2147483647 a signed 32 bit integer holds, so the distances need 64 bits. The owner is a junction number below 50000 and fits in 32 bits comfortably, which is a reason to keep the two fields separate rather than packing them into one number.

## Cost

O(m log n) for one search, with O(n) memory for the two key arrays.

Constraints - `1 ≤ n ≤ 50000` - `0 ≤ m ≤ 100000` - `1 ≤ k ≤ n` - `1 ≤ u, v ≤ n` - `0 ≤ w ≤ 1000000000` - The depot junctions are distinct.