Купоны на дороги


Отправить решение Решать в редакторе

Сложность: 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

Комментарии

Еще нет ни одного комментария.