← 返回题目列表

Codeforces · 1715/E

E. 漫漫长路回家

中文机器翻译题面 查看原题

Stanley 生活在一个由 $$$n$$$ 个城市组成的国家(他住在 $$$1$$$ 城市)。有些城市之间有双向道路,您知道骑车穿过每个城市需要多长时间。此外,每对城市之间都有一个航班,城市 $$$u$$$ 和 $$$v$$$ 之间的航班需要 $$$(u - v)^2$$$ 时间。

Stanley因为最近看了《萨利机长:哈德逊河奇迹》,对坐飞机相当害怕,所以他最多只能乘坐$$$k$$$航班。 Stanley 想知道从 $$$1$$$ 城市到每个 $$$n$$$ 城市的最短旅行时间。

输入

输入的第一行有三个整数 $$$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$$$ 的最短时间。

示例

输入 #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

注意

在第一个样本中,到达城市 1 不需要时间;要到达城市 2,可以乘坐 1 和 2 之间的航班,需要 1 个单位时间;您可以从城市 1 通过一条道路到达城市 3,这将需要 1 个单位时间。

在第二个示例中,到达城市 1 也不需要时间。要到达城市 2 Stanley,应使用 1 和 2 之间的航班,这将花费 1 个时间单位。要到达城市 3,斯坦利可以乘坐城市 1 和 2 之间的航班,需要 3 个单位时间,然后乘坐 2 和 3 之间的航班。要到达城市 4 斯坦利,应该乘坐城市 1 和 2 之间的航班,然后乘坐从 2 到 4 的航班,需要 5 个单位时间。