1686. How Far Is the Nearest Depot
A road network has n junctions and m two-way roads, all of equal length.
k of the junctions hold a DEPOT. For every junction, print how many roads away
its nearest depot is, on one line separated by single spaces. Print -1 for a
junction that can reach no depot at all. A junction holding a depot prints 0.
5 junctions, depots at 1 and 5
1 - 2 2 - 3 3 - 4 4 - 5 -> 0 1 2 1 0
## 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, and a second copy changes nothing when every road
has the same length.
unreachable? yes, per junction: a piece of the network holding no depot
prints -1 throughout. When n is 1 that junction must itself
hold the depot, so the answer is the single number 0.
## What most people try first
One search per depot, keeping a running minimum. That is correct and it costs
k times as much: with k at n it is O(n * (n + m)), which at the limits
is about 5 * 10^9 steps.
The second instinct is to search from every JUNCTION towards the depots, which is the same cost from the other side and harder to write.
## Seed the queue with all of them at once
Breadth-first search does not need a single starting point. Put EVERY depot in the queue at distance 0 and run the search exactly as usual:
for every depot d: dist[d] = 0, push d
while the queue is not empty:
u = pop
for each road (u, v):
if dist[v] is unset: dist[v] = dist[u] + 1, push v
One pass, O(n + m), whatever k is.
## Why seeding many sources is still correct
The invariant breadth-first search relies on is that the queue holds vertices in non-decreasing order of distance, and that is still true: it starts holding several vertices all at distance 0, which is non-decreasing, and every push adds one more than the value just popped. So the first time a junction is reached, it is reached at its smallest distance to ANY seed, which is exactly the distance-to-nearest-depot being asked for.
Equivalently, imagine one artificial junction joined to every depot by a road of length 0 and search from it. Seeding is that construction with the artificial junction optimised away, and the two give identical answers.
## What this is not
Problem 377 also seeds many sources, on a GRID, and prints a single number: the minute the last fresh cell is reached, or -1 if one never is. This prints the whole array and has no notion of a blocked cell, so an unreachable junction is reported in place rather than collapsing the whole answer. Problem 392 prints the largest distance from ONE fixed source, and problem 364 the distance between one pair.
## Cost
O(n + m) time and O(n) memory. A distance is at most n - 1 = 49999, so 32
bit arithmetic is ample throughout.
Constraints - `1 ≤ n ≤ 50000` - `0 ≤ m ≤ 100000` - `1 ≤ k ≤ n` - `1 ≤ u, v ≤ n` - The depot junctions are distinct.
Input
The first line contains three integers n, m and k.
The second line contains k distinct integers, the junctions holding a depot.
Each of the next m lines contains two integers u and v: a two-way road between u and v.
Output
Print n integers on one line separated by single spaces. The ith is the number of roads from junction i to its nearest depot, or -1 if no depot can be reached from it.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.