1688. Which Depot Is Worth Opening

A network has n junctions and m two-way roads with non-negative travel costs. There are k candidate depots; depot i sits at junction d[i] and costs c[i] to OPEN. Exactly one depot is opened, and a delivery then travels from it to junction n.

Print the smallest total of the opening cost plus the travel cost, or -1 if no depot can reach junction n.

``` 5 junctions, every road costing 1 depot at 1 costs 0, depot at 5 costs 100

-> 4 open the free depot at junction 1 and drive four roads ```

Moving the free depot to junction 5 and charging 100 at junction 1 instead makes the answer 0: no travel at all. The opening costs and the travel costs trade off against each other, which is the whole problem.

## The four things that have to be said

directed? no. Every road may be driven either way. self-loops? allowed, and never on a cheapest route. parallel roads? allowed, at different costs, and the cheaper copy wins. unreachable? yes. If no candidate depot can reach junction n, print -1. Note that a depot AT junction n is always usable, so the answer is then at most its opening cost. When n is 1 the answer is the smallest opening cost among depots at junction 1, and -1 if there is none.

## What most people try first

One Dijkstra run per candidate depot, adding the opening cost at the end and taking the minimum. That is correct, and it is what the expected answers here were checked against. It costs O(k * m log n), which at k = n = 50000 and m = 100000 is far too slow.

The second instinct is to seed every depot at distance 0, as in problem 1687, and add the opening cost afterwards. That is wrong, and the reason is worth being precise about: seeding at 0 makes the search choose the NEAREST depot, while the question wants the one minimising cost PLUS travel. A depot that is near and expensive loses to one that is far and free, and a search seeded at 0 has already committed to the near one before the opening cost is consulted.

## Seed each depot at its own opening cost

The fix is one line, and it is the general shape of this pattern.

for each candidate depot (d, c): dist[d] = min(dist[d], c), push (c, d) run Dijkstra exactly as usual answer = dist[n]

Equivalently, and this is the way to think about it: add ONE ARTIFICIAL JUNCTION numbered 0, join it to depot d[i] by a one-way road of cost c[i], and run an ordinary single-source search from junction 0. Then

dist(0, n) = min over i of ( c[i] + dist(d[i], n) )

which is exactly the quantity asked for, because every route out of junction 0 begins by paying exactly one opening cost.

## Why the artificial junction is legitimate

It adds 1 vertex and k edges, so the graph grows by O(k) and the cost of the search is unchanged in order. Its edges are one-way, out of junction 0 only, so nothing can route THROUGH it: a route is forced to leave it once, at the start, and never return. That one-way detail is what makes the construction answer the right question, and making those edges two-way would let a route hop between depots for the price of two opening costs.

Note also the min when seeding directly: two candidate depots may sit at the same junction at different opening costs, and only the cheaper matters.

## Overflow, computed rather than assumed

A cheapest route is simple, so it uses at most n - 1 = 49999 roads of up to 10^9, which is about 5 * 10^13, and one opening cost of up to 10^9 is added to that. The total stays near 5 * 10^13, far past the 2147483647 a signed 32 bit integer holds, so the distances need 64 bits.

## Cost

O((m + k) log n) for the single search, against O(k * m log n) for one run per depot, with O(n + m + k) memory.

Constraints - `1 ≤ n ≤ 50000` - `0 ≤ m ≤ 100000` - `1 ≤ k ≤ n` - `1 ≤ d ≤ n` - `0 ≤ c ≤ 1000000000` - `0 ≤ w ≤ 1000000000`