Купоны на дороги
Отправить решение
Решать в редакторе
Сложность:
40%
Очки:
100 (частичный балл)
Ограничение по времени:
5.0s
Ограничение по памяти:
256M
Автор:
Тип задачи
Разрешённые языки
C, C#, C++, F#, Go, Java, JavaScript, Kotlin, Pascal, Python, Scratch
Купоны на дороги
Между n городами m двусторонних платных дорог. У вас c купонов; купон снижает стоимость одной дороги вдвое с округлением вниз (w → ⌊ w/2 ⌋). На одну дорогу применить можно не более одного купона, а один и тот же проезд по дороге оплачивается отдельно. Найдите наименьшую стоимость поездки из города 1 в город n.
Ввод. В первой строке n, m, c (2 ≤ n ≤ 3· 10⁴, 0 ≤ m ≤ 6· 10⁴, 0 ≤ c ≤ 10). Далее m строк a b w (1 ≤ w ≤ 10⁶).
Вывод. Одно число или -1.
Пример 1
Ввод
4 4 1
1 2 10
2 4 10
1 3 8
3 4 14
Вывод
15
Комментарии