There are n cities 1 .. n and one-way flights (a, b, c) costing c >= 1. You hold one coupon that halves the price of a single flight, rounding down (c // 2). City n is always reachable from city 1.
Write flight_discount(n, flights) -> int returning the cheapest cost from city 1 to city n when the coupon is used optimally.
flights = [(1, 2, 3), (2, 3, 1), (1, 3, 7), (2, 1, 5)]
flight_discount(3, flights) # 2 (coupon on 1 -> 2 turns 3 into 1, then 2 -> 3 costs 1)
Constraints: 2 <= n <= 30_000, up to 80_000 flights, 1 <= c <= 10**9 (Python ints handle the sums). Trying each flight as the discounted one and re-solving from scratch is far too slow; aim for O((V + E) log V).
Show hint
a normal shortest-path search can't tell whether the coupon is still available. Make that part of where you are: each city appears twice, once with the coupon unused and once with it used.