← 返回题目
题库练习 Long Way Home
← 上一题 下一题 →

A15346 | Long Way Home

时间限制1s
内存限制256MB
通过 / 提交0/0

题目描述

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
C++ 编辑器
输入
输出