CF1715E Long Way Home

Stanley 住在一个由 $n$ 个城市组成的国家（他住在城市 $1$）。有一些城市之间有双向道路，你知道通过每条道路所需的时间。此外，每对城市之间都有一条航班，城市 $u$ 和 $v$ 之间的航班需要 $(u-v)^2$ 的时间。 Stanley 最近因为看了《萨利机长：哈德逊奇迹》而对飞行感到害怕，所以他最多只能乘坐 $k$ 次航班。Stanley 想知道从城市 $1$ 出发到每个城市的最短旅行时间。

输入的第一行包含三个整数 $n$、$m$ 和 $k$（$2 \leq n \leq 10^{5}$，$1 \leq m \leq 10^{5}$，$1 \leq k \leq 20$），分别表示城市数量、道路数量和 Stanley 最多可以乘坐的航班次数。 接下来的 $m$ 行描述道路。每行包含三个整数 $u$、$v$、$w$（$1 \leq u, v \leq n$，$u \neq v$，$1 \leq w \leq 10^{9}$），表示一条连接城市 $u$ 和 $v$ 的道路，以及通过这条道路所需的时间 $w$。注意，有些城市对之间可能有多条道路。

输出 $n$ 个整数，第 $i$ 个整数表示从城市 $1$ 出发到城市 $i$ 的最短旅行时间。

在第一个样例中，到达城市 $1$ 不需要时间；到达城市 $2$ 可以乘坐 $1$ 到 $2$ 的航班，需要 $1$ 单位时间；到达城市 $3$ 可以通过城市 $1$ 的道路到达，需要 $1$ 单位时间。 在第二个样例中，到达城市 $1$ 也不需要时间。到达城市 $2$，Stanley 应该乘坐 $1$ 到 $2$ 的航班，需要 $1$ 单位时间。到达城市 $3$，Stanley 可以先从城市 $1$ 到 $2$，需要 $3$ 单位时间，然后乘坐 $2$ 到 $3$ 的航班。到达城市 $4$，Stanley 应该先乘坐 $1$ 到 $2$ 的航班，然后从 $2$ 到 $4$，总共需要 $5$ 单位时间。 由 ChatGPT 4.1 翻译