1690. The Closest Pair Across Two Lists

A network has n junctions and m two-way roads with non-negative travel times. p junctions are WAREHOUSES and q junctions are SHOPS. A junction may be both.

Print the smallest travel time between any warehouse and any shop, or -1 if no warehouse can reach any shop.

5 junctions, warehouses at 1 and 2, shops at 4 and 5 1 - 2 (1) 2 - 3 (1) 3 - 4 (1) 4 - 5 (1) -> 2

Warehouse 2 to shop 4 is two roads, and no pair is closer.

## 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. Print -1 when no warehouse is in the same piece as any shop. When n is 1 that junction is the only candidate for both lists, and if it is in both the answer is 0.

## The case where the answer is 0

A junction may be both a warehouse and a shop, and then the pair is that junction with itself, at distance 0. Checking that before any search is cheaper than discovering it, and forgetting it is the most common way to get this problem wrong on a small input.

## What most people try first

A search from every warehouse, taking the minimum over shops. That is O(p * m log n), and with p at n it is far too slow. Running from every shop instead is the same cost from the other side.

## One search with every warehouse seeded, and that is all

Seed all p warehouses at distance 0, as in problem 1687, run one Dijkstra, and take the smallest distance over the q shops:

for each warehouse w: dist[w] = 0, push (0, w) run Dijkstra unchanged answer = min over shops s of dist[s]

## Why no second artificial vertex is needed

Problem 1688 adds one artificial vertex for the source side, and it is tempting to add a second for the target side and read off a single distance. It is not necessary here, and seeing why is the point of this problem.

An artificial vertex earns its place when the endpoints carry DIFFERENT costs, as the opening costs do in problem 1688 and the entry and exit fees do in problem 1693. Here every warehouse and every shop is equally acceptable at no charge, so the target side needs no cost at all, and taking a minimum over q already-computed distances is a loop of length q.

Better still, the search can stop the moment the first SHOP is popped from the heap. Dijkstra pops vertices in non-decreasing order of distance, so the first shop popped is the nearest one, and nothing after it can be closer. That turns the final loop into an early exit.

## 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. The distances need 64 bits; a single road time of 10^9 does not.

## Cost

O(m log n) for one search plus O(q) for the final minimum, or O(m log n) with the early exit. Memory O(n + m).

Constraints - `1 ≤ n ≤ 50000` - `0 ≤ m ≤ 100000` - `1 ≤ p, q ≤ n` - `1 ≤ u, v ≤ n` - `0 ≤ w ≤ 1000000000` - The warehouse junctions are distinct, and so are the shop junctions.