One free ride
There are m toll roads between n towns; each can be driven both ways and has its own toll. You have one coupon: it makes any one road on your way free. How much will you have to pay to get from town 1 to town n if you spend the coupon wisely?
Input
The first line holds n and m (2 ≤ n ≤ 50,000, 1 ≤ m ≤ 100,000). Then m lines a b c—a road between towns a and b with a toll of c (1 ≤ c ≤ 10⁶).
Output
The smallest amount you will have to pay, or -1 if town n cannot be reached from 1. You may leave the coupon unused, but using it always pays off if you drive at least one road.
Examples
Example 1
4 4 1 2 3 2 3 50 3 4 2 1 4 60
0
Example 2
4 4 1 2 10 2 4 10 1 3 1 3 4 100
1
Limits
- Time · Python
- 5000 ms
- Time · Go
- 1500 ms
- Memory
- 256 MB
- Judging
- 9 tests
Walkthrough
Open it step by step: each step gives away a little more. You can jump straight to the solution, but a problem solved with one hint stays with you longer.
1Hint 1
The obvious solution: find the cheapest route and make the most expensive road on it free. Try it on the second example.
2Hint 2
To know how much you can still save, it is not enough to know which town you are in. What else do you need to remember about the way so far?
3The idea
The traveller's state is a pair “town, coupon spent or not”. Build a graph on such pairs: from (u, 0) along a road (u, v, c) you can get to (v, 0) for c or to (v, 1) for free, and from (u, 1) only to (v, 1) for c. These are two floors of one graph, and the coupon is a staircase from the first floor to the second. The answer is the shortest path from (1, 0) to either of (n, 0), (n, 1). Ordinary Dijkstra finds it: all weights are non-negative.
4Walkthrough
The graph on pairs need not be built explicitly: the neighbours of a pair are easy to list on the fly. Keep dist[v][used], and put triples (distance, town, flag) on the heap. When handling (u, used), try two moves for every road: pay, and, if the coupon is still whole, go for free.
Why the greedy idea from the first hint is wrong: in the second example the cheapest route 1 → 2 → 4 costs 20, and the coupon takes 10 off it. The route 1 → 3 → 4 costs 101, but the coupon takes 100 off it, leaving 1. The coupon changes which route is the cheapest, so the two problems cannot be solved one after the other.
The same trick works for k coupons (k + 1 floors), for “at most k changes”, for “the fuel lasts L kilometres”—anything where a vertex needs a little memory of the way so far.
4+Solution
5Complexity
There are 2n states and at most 3 moves for each direction of a road: O((n + m) log n). For k coupons, k + 1 times more.
6Common mistakes
- A discount on the most expensive road of the cheapest route. Fails the second example—see the walkthrough.
- Overflow. The total reaches 5·10¹⁰: Go's
intis 64 bits and copes, but in languages with a 32-bitintthe answer to the eighth test breaks. - One distance per town instead of two. Then the way “cheap, but the coupon is spent” overwrites the way “a little dearer, but the coupon is whole”, although the second may save far more later. States with different flags must live apart.