Long Way Home

题意翻译

有 $n$ 座城市，城市间有 $m$ 条双向道路，通过第 $i$ 条道路需要花费 $w_i$ 的时间，任意两个城市之间都有航班，乘坐城市 $u$ 和 $v$ 之间的航班需要花费 $(u-v)^2$ 的时间。 现在请对于任意城市 $i(1 \le i \le n)$，求出从城市 $1$ 出发，到达城市 $i$ 所需要的最短时间，注意从城市 $1$ 到 $i$ 的过程中**最多乘坐 $k$ 次航班**。

题目描述

Stanley lives in a country that consists of $ n $ cities (he lives in city $ 1 $ ). 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 $ (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 $ 1 $ .

输入输出格式

输入格式

In the first line of input there are three integers $ n $ , $ m $ , and $ k $ ( $ 2 \leq n \leq 10^{5} $ , $ 1 \leq m \leq 10^{5} $ , $ 1 \leq k \leq 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 \leq u, v \leq n $ , $ u \neq v $ , $ 1 \leq w \leq 10^{9} $ ) — 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 $ .

输入输出样例

输入样例 #1

3 1 2
1 3 1

输出样例 #1

0 1 1

输入样例 #2

4 3 1
1 2 3
2 4 5
3 4 7

输出样例 #2

0 1 4 6

输入样例 #3

2 1 1
2 1 893746473

输出样例 #3

0 1

输入样例 #4

5 5 2
2 1 33
1 5 93
5 3 48
2 3 21
4 2 1

输出样例 #4

0 1 2 2 3

说明

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.

**题目大意：**
有 $ n $ 座城市和 $ m $ 条双向道路，道路 $ i $ 需要花费 $ w_i $ 的时间。任意两个城市之间都有航班，乘坐城市 $ u $ 和 $ v $ 之间的航班需要花费 $ (u-v)^2 $ 的时间。需要求出从城市 $ 1 $ 出发，到达任意城市 $ i $ 的最短时间，其中最多乘坐 $ k $ 次航班。

**输入格式：**
第一行包含三个整数 $ n $、$ m $ 和 $ k $，分别表示城市数量、道路数量和最大乘坐航班次数。接下来 $ m $ 行，每行三个整数 $ u $、$ v $ 和 $ w $，表示城市 $ u $ 和 $ v $ 之间有一条需要 $ w $ 时间的道路。

**输出格式：**
输出 $ n $ 个整数，第 $ i $ 个整数表示到达城市 $ i $ 的最短时间。

**输入输出样例：**
- 输入样例 #1：
```
3 1 2
1 3 1
```
输出样例 #1：
```
0 1 1
```
- 输入样例 #2：
```
4 3 1
1 2 3
2 4 5
3 4 7
```
输出样例 #2：
```
0 1 4 6
```
- 输入样例 #3：
```
2 1 1
2 1 893746473
```
输出样例 #3：
```
0 1
```
- 输入样例 #4：
```
5 5 2
2 1 33
1 5 93
5 3 48
2 3 21
4 2 1
```
输出样例 #4：
```
0 1 2 2 3
```**题目大意：** 有 $ n $ 座城市和 $ m $ 条双向道路，道路 $ i $ 需要花费 $ w_i $ 的时间。任意两个城市之间都有航班，乘坐城市 $ u $ 和 $ v $ 之间的航班需要花费 $ (u-v)^2 $ 的时间。需要求出从城市 $ 1 $ 出发，到达任意城市 $ i $ 的最短时间，其中最多乘坐 $ k $ 次航班。 **输入格式：** 第一行包含三个整数 $ n $、$ m $ 和 $ k $，分别表示城市数量、道路数量和最大乘坐航班次数。接下来 $ m $ 行，每行三个整数 $ u $、$ v $ 和 $ w $，表示城市 $ u $ 和 $ v $ 之间有一条需要 $ w $ 时间的道路。 **输出格式：** 输出 $ n $ 个整数，第 $ i $ 个整数表示到达城市 $ i $ 的最短时间。 **输入输出样例：** - 输入样例 #1： ``` 3 1 2 1 3 1 ``` 输出样例 #1： ``` 0 1 1 ``` - 输入样例 #2： ``` 4 3 1 1 2 3 2 4 5 3 4 7 ``` 输出样例 #2： ``` 0 1 4 6 ``` - 输入样例 #3： ``` 2 1 1 2 1 893746473 ``` 输出样例 #3： ``` 0 1 ``` - 输入样例 #4： ``` 5 5 2 2 1 33 1 5 93 5 3 48 2 3 21 4 2 1 ``` 输出样例 #4： ``` 0 1 2 2 3 ```