1656. Cheapest Route While Collecting Keys

A building has n rooms joined by m two-way corridors. Corridor (u, v, w, need) takes w seconds to walk and is locked by key number need, or is unlocked when need is 0. A room may hold one key, which is picked up free the moment you stand in the room and is never put down.

Print the least time to get from room 1 to room n, or -1 if it cannot be done.

4 rooms, 1 key. Room 2 holds key 1. 1 - 2 (1, open) 2 - 3 (1, open) 3 - 4 (1, needs key 1) 1 - 4 (1, needs key 1) -> 3

The direct corridor 1 - 4 is locked and you have no key at room 1, so the answer is to fetch the key at room 2 and then walk on.

## The four things that have to be said

directed? no. Every corridor may be walked either way, and needs the same key in both directions. self-loops? allowed, and never useful. parallel edges? allowed, and a pair of rooms may be joined by one open corridor and one locked one. unreachable? yes, in two ways. Room n may sit in another piece, or every route may be blocked by a key that is itself behind a locked corridor. Print -1 for both. When n is 1 the answer is 0.

## What most people try first

Dijkstra over the rooms, skipping any corridor whose key you do not hold. That needs a notion of "hold" that the search does not have, and whatever it does have is wrong: a room reached quickly without the key and a room reached slowly WITH the key are not interchangeable, and one number per room keeps only one of them.

The second instinct is to fetch keys greedily, nearest first. That fails for the usual greedy reason: the nearest key may be useless on your route while a further one opens the door you need.

## The node of the search is a pair

Search the PRODUCT graph whose vertices are pairs (room, set of keys held). The set is a bitmask of K bits, so the product graph has n * 2^K vertices, which at the limits is 2000 * 256 = 512000 states.

from state (u, S), for each corridor (u, v, w, need): if need is not 0 and bit need-1 is clear in S: the corridor is locked, skip arriving at v also picks up v's key, so the new set is S' = S | key(v) arc (u, S) -> (v, S') of cost w

The start state is (1, key(1)), because room 1's key is picked up before anything else happens. The answer is the smallest distance over all states (n, S), since any set of keys is an acceptable way to arrive.

## Why a set and not a count

Counting how many keys you hold is not enough: which keys you hold decides which corridors open. And the set only ever grows, because a key is never put down, so the product graph has no cycle in its second coordinate and a state is reachable from at most the states with a subset of its keys.

Every arc cost is non-negative, so Dijkstra is correct on the product graph exactly as it stands.

## Overflow, computed rather than assumed

A cheapest route never repeats a product state, so it uses at most n * 2^K - 1 corridors, which is 511999. Each takes up to 10^4 seconds, so a total can reach about 5.1 * 10^9. That is PAST the 2147483647 a signed 32 bit integer holds, so the distances need 64 bits. The individual weights do not: a single 10^4 is tiny.

## Cost

O(m * 2^K * log(n * 2^K)) time and O(n * 2^K) memory, about 4 * 10^7 heap operations at the limits.

Constraints - `1 ≤ n ≤ 2000` - `0 ≤ m ≤ 10000` - `0 ≤ K ≤ 8` - `0 ≤ w ≤ 10000` - Each room holds 0 or 1 keys, and two rooms may hold the same key number.