n городов с номерами от 0 до n - 1. Они соединены платными дорогами: roads[i] = [a, b, toll] означает, что между городами a и b есть двусторонняя дорога и проезд по ней стоит toll.
У вас есть coupons купонов. Купон, предъявленный на дороге, снижает плату за неё до toll // 2 (с округлением вниз). Каждый купон одноразовый, и на одну поездку по дороге можно предъявить не больше одного купона.
Верните минимальную сумму, которую придётся заплатить, чтобы доехать из города 0 в город n - 1, или -1, если доехать нельзя.n=4, roads=[[0, 1, 10], [1, 3, 10], [0, 2, 3], [2, 3, 19]], coupons=1 → 12
Через город 2: 3 + 19 // 2 = 3 + 9 = 12. Через город 1: 10 + 10 // 2 = 15. Ответ 12.
n=3, roads=[[0, 1, 7], [1, 2, 5]], coupons=5 → 5
Купонов хватает на обе дороги: 7 // 2 + 5 // 2 = 3 + 2 = 5.
n=3, roads=[[0, 1, 4]], coupons=2 → -1
До города 2 дорог нет, поэтому ответ -1.
n=4, roads=[[0, 1, 10], [1, 3, 10], [0, 2, 3], [2, 3, 19]], coupons=1
12
«Запустить» — первые 3 теста у тебя в браузере, «Отправить» — все 83 теста на сервере, включая скрытые.