1661. No Two Legs of the Same Colour

A network has n hubs and m two-way legs. Leg (u, v, c, w) is operated by carrier c, one of C carriers, and takes w hours. No two CONSECUTIVE legs of a journey may be operated by the same carrier.

Print the least total hours from hub 1 to hub n, or -1 if no legal journey exists.

4 hubs, 2 carriers 1 - 2 carrier 1 (1) 2 - 4 carrier 2 (1) 1 - 3 carrier 1 (5) 3 - 4 carrier 1 (5) -> 2

The route 1 - 3 - 4 is illegal: both legs are carrier 1. The route 1 - 2 - 4 alternates carriers and costs 2.

## The four things that have to be said

directed? no. Every leg may be flown either way, keeping its carrier. self-loops? allowed, and only ever a way to change carrier in place at a price. parallel legs? allowed, and a pair of hubs joined by two carriers is what makes the constraint escapable. unreachable? yes, in two ways. Hub n may sit in another piece, or every route to it may be forced to repeat a carrier. Print -1 for both. When n is 1 the answer is 0, since no leg is flown.

## What most people try first

Dijkstra over the hubs, refusing a leg whose carrier matches the one that got you here. The rule is right and the place is wrong: the hub does not record which carrier got you there, and a cheap arrival by carrier 1 and a dearer arrival by carrier 2 are not interchangeable when the only leg out is carrier 1. One number per hub keeps the cheap arrival, which may be the one that is stuck.

The second instinct is to delete, for each leg, the legs of the same carrier next to it, and search what remains. That cannot be done consistently, because whether a leg is usable depends on the route, not on the network.

## The node of the search is a pair

Search the PRODUCT graph whose vertices are pairs (hub, carrier of the last leg), with a value 0 meaning no leg flown yet. Its size is n * (C + 1), which at the limits is 5000 * 11 = 55000 states.

for each leg (u, v, c, w) and each last carrier L with L != c: arc (u, L) -> (v, c) of cost w arc (v, L) -> (u, c) of cost w start (1, 0) answer the smallest distance over all states (n, L)

The condition L != c is the entire rule, enforced once, on the arc. The value 0 is never the carrier of any leg, so it never blocks the first leg, which is exactly what is wanted.

## Why the last carrier is all that has to be remembered

The rule constrains only CONSECUTIVE legs, so nothing about the earlier part of the journey can matter. That is what keeps the state small: there is no need to remember the whole sequence of carriers, only the most recent one, and that is the general shape of this pattern. A rule about the last two legs would need (hub, last, second last) and n * (C + 1)^2 states, and a rule about the whole history would not be a shortest-path problem at all.

Every arc cost is non-negative, so Dijkstra is correct on the product graph unchanged.

## Overflow, computed rather than assumed

The product graph has n * (C + 1) = 55000 states, so a cheapest journey uses at most 54999 legs, each up to 10^6 hours. The total can reach about 5.5 * 10^10, past the 2147483647 a signed 32 bit integer holds, so the distances need 64 bits. A single weight of 10^6 fits in 32 bits easily.

## Cost

O(m * C * log(n * C)) time and O(n * C) memory, about 10^6 heap operations at the limits.

Constraints - `1 ≤ n ≤ 5000` - `0 ≤ m ≤ 20000` - `1 ≤ C ≤ 10` - `1 ≤ c ≤ C` - `0 ≤ w ≤ 1000000`