Codeforces Round 816 (Div. 2) |
---|
Закончено |
Олеся решила отправиться в путешествие по стране, состоящей из $$$n$$$ городов (она живет в городе $$$1$$$). Между некоторыми городами страны есть двусторонние дороги. Для каждой дороги известно время, необходимое для того, чтобы по ней проехать. Также между каждой парой городов есть авиарейс, перелет из города $$$u$$$ в город $$$v$$$ занимает $$$(u - v)^2$$$ времени.
Олеся недавно посмотрела «Чудо на Гудзоне» и несколько боится летать, поэтому она может воспользоваться не более чем $$$k$$$ перелетами. Олеся хочет узнать минимальное время путешествия в каждый из $$$n$$$ городов страны из города $$$1$$$.
В первой строке находятся числа $$$n$$$, $$$m$$$ и $$$k$$$ ($$$2 \leq n \leq 10^{5}$$$, $$$1 \leq m \leq 10^{5}$$$, $$$1 \leq k \leq 20$$$) — количество городов, дорог и максимальное количество перелётов, которое может совершить Олеся.
Следующие $$$m$$$ строк описывают дороги. В каждой находятся числа $$$u$$$, $$$v$$$, $$$w$$$ ($$$1 \leq u, v \leq n$$$, $$$u \neq v$$$, $$$1 \leq w \leq 10^{9}$$$) — города, которые соединяет дорога, и время, необходимое, чтобы по ней проехать. Некоторые пары городов могут быть соединены более чем одной парой дорог.
Выведите $$$n$$$ чисел, $$$i$$$-е из которых равно минимальному времени путешествия в город $$$i$$$.
3 1 2 1 3 1
0 1 1
4 3 1 1 2 3 2 4 5 3 4 7
0 1 4 6
2 1 1 2 1 893746473
0 1
5 5 2 2 1 33 1 5 93 5 3 48 2 3 21 4 2 1
0 1 2 2 3
В первом примере время путешествия до города 1 равно 0; чтобы добраться в город 2, можно воспользоваться авиаперелетом из 1 в 2 за 1 единицу времени; в город 3 можно добраться из города 1 по дороге за 1 единицу времени.
Во втором примере время путешествия до города 1 равно 0. Чтобы добраться в город 2, можно воспользоваться авиаперелетом из 1 в 2, занимающим 1 единицу времени. Чтобы добраться в город 3 за 4 единицы времени, можно проехать из города 1 в город 2 по дороге за 3 единицы времени, а потом воспользоваться авиаперелетом из 2 в 3. Чтобы добраться в город 4, можно воспользоваться авиаперелетом из города 1 в город 2, а потом проехать из города 2 в город 4 по дороге за 5 единиц времени.
Название |
---|