1657. Cheapest Route of Even Length

An undirected graph has n vertices and m weighted edges. Print the smallest total weight of a route from vertex 1 to vertex n that uses an EVEN number of edges, or -1 if there is no such route.

Vertices and edges may be repeated, so a route is a walk.

4 vertices 1 - 2 (1) 2 - 4 (1) 1 - 3 (5) 3 - 4 (5) -> 2

Both routes have two edges, and the cheap one costs 2.

## The four things that have to be said

directed? no. Every edge may be walked either way, and walking out and back is a legal pair of edges. self-loops? allowed. One adds a single edge, so it flips the parity. parallel edges? allowed, at different weights. unreachable? yes, in two ways. Vertex n may sit in another piece, or every walk to it may have odd length, which happens on a bipartite graph where 1 and n are on opposite sides. Print -1 for both. When n is 1 the answer is 0, since zero edges is even.

## What most people try first

Dijkstra, then check whether the route it found happens to have even length. It usually does not, and there is nothing to do about it afterwards: a shortest-path algorithm has already thrown the edge count away, so you cannot ask it for a different route.

The next attempt counts edges alongside the distance and keeps the better pair per vertex. That fails because the two objectives are not comparable: a cheap odd arrival and a dear even arrival are both worth keeping, and whichever one a single slot holds is wrong half the time.

## The node of the search is a pair

Search the PRODUCT graph whose vertices are pairs (vertex, parity), where parity is 0 or 1 for the number of edges used so far. Its size is exactly 2 * n, which is 100000 states at the limits.

for each edge (u, v, w) and each parity p: arc (u, p) -> (v, 1 - p) of cost w arc (v, p) -> (u, 1 - p) of cost w start (1, 0) answer dist[(n, 0)]

Every arc flips the parity, because every arc is one edge. Weights are non-negative, so Dijkstra is correct on the product graph unchanged.

## Why two copies of the graph is the right picture

Think of it as two layers, an even layer and an odd layer, with every edge of the original graph joining the two layers rather than staying inside one. Walking is then forced to alternate layers, so arriving in the even layer means exactly that you used an even number of edges. The answer is the even-layer entry for vertex n, and the odd-layer entry for the same vertex is a different, equally real number that simply answers a different question.

## When the answer is genuinely -1 rather than a bug

On a graph where 1 and n lie on opposite sides of a two-colouring, every walk between them has odd length, so no even walk exists at any price and -1 is the truthful answer. The test 2 1 / 1 2 1 is the smallest instance: the only walks are 1 edge, 3 edges, 5 edges, all odd. That is the case most likely to send someone hunting for a bug that is not there.

## Overflow, computed rather than assumed

The product graph has 2n = 100000 states, so a cheapest walk uses at most 99999 edges, each of weight up to 10^9. The total can therefore reach about 10^14, far past the 2147483647 of a signed 32 bit integer, so the distances need 64 bits. A single weight of 10^9 fits in 32 bits comfortably, and so would 2 * 10^9; it is the accumulation that does not.

## Cost

O(m log n) with a constant factor of two for the layers, and O(n) memory.

Constraints - `1 ≤ n ≤ 50000` - `0 ≤ m ≤ 100000` - `1 ≤ u, v ≤ n` - `0 ≤ w ≤ 1000000000`