n городов с номерами от 0 до n - 1 и двусторонние платные дороги: roads[i] = [a, b, cost] соединяет города a и b, проезд по ней стоит cost. Из любого города можно доехать до любого другого, между двумя городами не больше одной дороги, дорог из города в него же нет.
У путешественника есть passes пропусков. Пропуск делает проезд по одной дороге бесплатным, и на маршруте можно использовать не больше passes пропусков.
Верните наименьшую сумму, которую придётся заплатить, чтобы доехать из города start в город finish.n=4, roads=[[0, 1, 5], [1, 3, 5], [0, 2, 1], [2, 3, 20]], start=0, finish=3, passes=1 → 1
Без пропусков лучший путь 0 → 1 → 3 стоит 10. С одним пропуском выгоднее 0 → 2 → 3: платим 1 за первую дорогу, а дорогу ценой 20 проезжаем бесплатно.
n=3, roads=[[0, 1, 7], [1, 2, 3]], start=0, finish=2, passes=0 → 10
Пропусков нет, и путь единственный: 7 + 3 = 10.
n=5, roads=[[0, 1, 4], [1, 2, 4], [2, 3, 4], [3, 4, 4]], start=0, finish=4, passes=2 → 8
Путь 0 → 1 → 2 → 3 → 4 из четырёх дорог по 4; две из них бесплатны, остаётся 8.
n ≤ 500roads.length ≤ min(10⁴, n·(n − 1)/2)a, b ≤ n − 1, a ≠ bcost ≤ 10⁶start, finish, passes ≤ n − 1, start ≠ finishn=4, roads=[[0, 1, 5], [1, 3, 5], [0, 2, 1], [2, 3, 20]], start=0, finish=3, passes=1
1
«Запустить» — первые 3 теста у тебя в браузере, «Отправить» — все 62 теста на сервере, включая скрытые.