n городов с номерами от 0 до n - 1, все они связаны сетью двусторонних дорог. Дорога roads[i] = [x, y, t] соединяет города x и y и занимает t минут. Между двумя городами может быть несколько дорог с разным временем, но дорог из города в него же нет.
Каждый раз, оказываясь в городе j, вы платите сбор fees[j] (в том числе в начальном и в конечном городе; если заехать в город повторно, платить придётся снова).
Вы стартуете из города 0 и должны добраться до города n - 1 не более чем за deadline минут. Верните минимальную сумму сборов за такую поездку или -1, если успеть невозможно.deadline=10, roads=[[0, 1, 2], [1, 3, 2], [0, 2, 4], [2, 3, 4]], fees=[1, 9, 2, 3] → 6
Через город 2 дорога занимает 8 минут и стоит 1 + 2 + 3 = 6, через город 1 — 4 минуты, но 1 + 9 + 3 = 13. Успеваем оба раза, выбираем дешёвый: 6.
deadline=5, roads=[[0, 1, 2], [1, 3, 2], [0, 2, 4], [2, 3, 4]], fees=[1, 9, 2, 3] → 13
Теперь путь через город 2 (8 минут) не укладывается в срок, остаётся только маршрут через город 1 за 13.
deadline=3, roads=[[0, 1, 4]], fees=[2, 2] → -1
Единственная дорога идёт 4 минуты — не успеть.
deadline ≤ 1000fees) ≤ 1000roads) ≤ 1000fees[j] ≤ 1000deadline=10, roads=[[0, 1, 2], [1, 3, 2], [0, 2, 4], [2, 3, 4]], fees=[1, 9, 2, 3]
6
«Запустить» — первые 3 теста у тебя в браузере, «Отправить» — все 100 тестов на сервере, включая скрытые.