1667. Which Edges the Route Actually Used

An undirected graph has n vertices and m edges, numbered 1 to m in the order they are given, every weight at least 1. More than one edge may join the same pair of vertices.

Print how many edges a cheapest route from vertex 1 to vertex n uses, then those edge NUMBERS in the order they are used, all on one line. Print -1 if there is no route.

Among all cheapest routes, print the one whose sequence of EDGE NUMBERS is smallest in dictionary order.

4 vertices, 5 edges 1: 1 - 2 (1) 2: 1 - 2 (5) 3: 2 - 3 (1) 4: 3 - 4 (1) 5: 1 - 4 (3) -> 3 1 3 4

Both 1 - 2 - 3 - 4 using edges 1, 3, 4 and the single edge 5 cost 3. The sequence 1 3 4 is smaller than 5 because 1 comes before 5, so three edges beat one.

## Why the vertex sequence is not enough here

Parallel edges are the point. Edges 1 and 2 both join vertices 1 and 2, so the vertex sequence 1 2 3 4 does not say which of them was taken, and two routes with the same vertices can have different costs. Problem 1663 prints vertices and cannot express this; that is the difference between the two.

So the parent recorded during the walk has to be the EDGE, not the predecessor vertex.

## The four things that have to be said

directed? no. Every edge may be walked either way, and it keeps its number in both directions. self-loops? allowed, and never on a cheapest route, since weights are at least 1. parallel edges? allowed and central, at different weights. unreachable? yes. Print -1. When n is 1 the answer is the single number 0: zero edges, and no numbers after it.

## The method

Run Dijkstra from vertex n over the plain weighted graph, giving distT[v]. Then walk forwards from vertex 1, choosing by edge number:

u = 1, used = [] while u != n: among edges e = (u, v, w) with w + distT[v] == distT[u], take the one with the SMALLEST NUMBER append its number, u = its other endpoint print the length of used, then used

The adjacency list has to carry the edge number alongside the destination and the weight, which is the only structural change from problem 1663.

## Why smallest-number-first is the dictionary minimum

An edge with w + distT[v] == distT[u] can still be completed at the optimal remaining cost, so taking any of them keeps the route cheapest. Which completions remain depends only on the vertex arrived at, never on how it was arrived at, so a larger edge number now cannot be repaid by smaller ones later. Taking the smallest usable number at each step therefore gives the smallest sequence.

Weights are at least 1, so distT strictly decreases along the walk and no vertex, and therefore no edge, can be used twice.

## Note that this is NOT the fewest edges

The example answers three edges where one would do, because the tie-break is on edge numbers and 1 beats 5. Problem 1668 is the version that ranks the edge COUNT above the sequence, and the two give different answers on exactly this input: 1668 prints the single edge, this prints three.

## Overflow, computed rather than assumed

A cheapest route is simple, so it uses at most n - 1 = 49999 edges of up to 10^9, and a total can reach about 5 * 10^13. That is far past the 2147483647 of a signed 32 bit integer, so the distances need 64 bits, even though the printed answer is a list of small numbers.

## Cost

O(m log n) for the search and O(m) for the walk, with O(m) memory for the adjacency list.

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