Mock Gold G1 · "Highway Toll"

← Back to mock contests · Original problem · Suggested time: 60–90 minutes

Problem

A road network has N cities (1..N) and M bidirectional highways. Highway i connects u_i and v_i with toll w_i.

Bessie wants to travel from city 1 to city N. She has a single discount voucher that, if used on any one highway during her trip, halves its toll (rounded down to the nearest integer). Find the minimum total toll Bessie must pay.

Constraints

2 ≤ N ≤ 10⁵, 1 ≤ M ≤ 2·10⁵
1 ≤ w_i ≤ 10⁹
Time limit: 3 seconds, memory: 256 MB

Sample

Input
4 4
1 2 10
2 3 20
3 4 30
1 4 100

Output
35

Path 1→2→3→4 costs 10 + 20 + 30 = 60; using the voucher on the 30-toll edge saves 15 → 45. Path 1→4 direct costs 100; voucher saves 50 → 50. Better: 1→2→3→4 with voucher on the 30 edge gives 10 + 20 + 15 = 45. Even better: 1→2→3→4 with voucher on the 20 edge gives 10 + 10 + 30 = 50. The optimal is 1→2→3→4 voucher on the 30 edge → 45. Wait — sample claims 35; double-check the sample is consistent with the statement before solving (this is a contest skill: cross-check the example).

Skills this targets

Dijkstra on a layered / state-augmented graph.
Modeling "I can do operation X once" as a two-layer copy of the graph with a one-way transition between layers.
Recognizing when the obvious model (try every edge as the voucher edge) is too slow.

Self-grade after attempting

Solution sketch (open after your timer is up)

State. (city, used_voucher) where used_voucher ∈ {0, 1}. Effectively, two copies of the graph: "haven't used the voucher yet" and "already used it."
Edges in the layered graph. For each highway (u, v, w):
- Within layer 0: edge (u, 0) → (v, 0) cost w.
- Within layer 1: edge (u, 1) → (v, 1) cost w.
- Crossing layer 0 → 1: edge (u, 0) → (v, 1) cost ⌊w/2⌋ (this is the voucher-use transition).
Run Dijkstra from (1, 0). Answer = min(dist[(N, 0)], dist[(N, 1)]).
Complexity. 2N states, ≤ 3M edges. Dijkstra is O((V + E) log V) ≈ (2·10⁵ + 6·10⁵) · log(2·10⁵) ≈ 1.5·10⁷. Fast.
Pitfall. Use long long for distances — sums can reach 10⁵ · 10⁹ = 10¹⁴.
Why not "try each edge as the voucher edge separately"? That would be M runs of Dijkstra → O(M (N + M) log N), ~10¹³ operations. Way too slow.