Table of Contents

## Long Way Home solution codeforces

**Long Way Home solution codeforces** – Stanley lives in a country that consists of 𝑛n cities (he lives in city 11). There are bidirectional roads between some of the cities, and you know how long it takes to ride through each of them. Additionally, there is a flight between each pair of cities, the flight between cities 𝑢u and 𝑣v takes (𝑢−𝑣)2(u−v)2 time.

Stanley is quite afraid of flying because of watching “Sully: Miracle on the Hudson” recently, so he can take at most 𝑘k flights. Stanley wants to know the minimum time of a journey to each of the 𝑛n cities from the city 11.

## [Solution] Long Way Home solution codeforces

In the first line of input there are three integers 𝑛n, 𝑚m, and 𝑘k (2≤𝑛≤1052≤n≤105, 1≤𝑚≤1051≤m≤105, 1≤𝑘≤201≤k≤20) — the number of cities, the number of roads, and the maximal number of flights Stanley can take.

The following 𝑚m lines describe the roads. Each contains three integers 𝑢u, 𝑣v, 𝑤w (1≤𝑢,𝑣≤𝑛1≤u,v≤n, 𝑢≠𝑣u≠v, 1≤𝑤≤1091≤w≤109) — the cities the road connects and the time it takes to ride through. Note that some pairs of cities may be connected by more than one road.

Print 𝑛n integers, 𝑖i-th of which is equal to the minimum time of traveling to city 𝑖i.

3 1 2 1 3 1

0 1 1

## [Solution] Long Way Home solution codeforces

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

## [Solution] Long Way Home solution codeforces

In the first sample, it takes no time to get to city 1; to get to city 2 it is possible to use a flight between 1 and 2, which will take 1 unit of time; to city 3 you can get via a road from city 1, which will take 1 unit of time.

In the second sample, it also takes no time to get to city 1. To get to city 2 Stanley should use a flight between 1 and 2, which will take 1 unit of time. To get to city 3 Stanley can ride between cities 1 and 2, which will take 3 units of time, and then use a flight between 2 and 3. To get to city 4 Stanley should use a flight between 1 and 2, then take a ride from 2 to 4, which will take 5 units of time.