You have a directed graph with N cities and M flights. Each flight has a cost. You get exactly one % discount coupon to use on any single flight.
Find the minimum cost to travel between city and city N.
Constraints: , M ≤ . You must decide where to use the coupon optimally. The challenge is that you cannot just pick the most expensive edge. The best discount depends on which path you take, so you need to consider all options simultaneously.