A7689. Roads and Gates
编程题
入门
知识点
题目描述
AtCoder 国有 $N$ 座城市和 $M$ 条道路。第 $i$ 条道路（$1\le i\le M$）双向连接城市 $u_i$ 和 $v_i$，从其中一端前往另一端需耗时 $T_i$ 分钟。
此外，每座城市均安装有一个传送门，可利用传送门从城市 $i$（$1\le i\le N$）前往城市 $j$（$1\le j\le N$），耗时为 $X_i+X_j+Y$ 分钟。
该国不存在其他城市间通行方式。
对每个 $k=2,3,\ldots,N$，求解以下问题：
* 求从城市 $1$ 到城市 $k$ 所需的最少时间。
在同一座城市内，由道路切换至另一条道路或传送门、或由传送门切换至另一条道路或传送门，所需换乘时间可忽略不计。
此外，每座城市均安装有一个传送门，可利用传送门从城市 $i$（$1\le i\le N$）前往城市 $j$（$1\le j\le N$），耗时为 $X_i+X_j+Y$ 分钟。
该国不存在其他城市间通行方式。
对每个 $k=2,3,\ldots,N$，求解以下问题：
* 求从城市 $1$ 到城市 $k$ 所需的最少时间。
在同一座城市内，由道路切换至另一条道路或传送门、或由传送门切换至另一条道路或传送门，所需换乘时间可忽略不计。
输入格式
输入从标准输入中按以下格式给出：
> $N$ $M$ $Y$
> $u _ 1$ $v _ 1$ $T _ 1$
> $u _ 2$ $v _ 2$ $T _ 2$
> $\vdots$
> $u _ M$ $v _ M$ $T _ M$
> $X _ 1$ $X _ 2$ $\ldots$ $X _ N$
> $N$ $M$ $Y$
> $u _ 1$ $v _ 1$ $T _ 1$
> $u _ 2$ $v _ 2$ $T _ 2$
> $\vdots$
> $u _ M$ $v _ M$ $T _ M$
> $X _ 1$ $X _ 2$ $\ldots$ $X _ N$
输出格式
按顺序输出 $k=2,3,\ldots,N$ 时各问题的答案，用空格分隔。
输入输出样例
输入 #1
7 7 3 1 2 1 1 3 6 2 3 4 3 5 8 3 7 4 4 5 2 4 7 9 3 1 4 1 5 9 2
输出 #1
1 5 6 8 14 7
输入 #2
2 0 1000000000 1000000000 1000000000
输出 #2
3000000000
输入 #3
12 20 873 2 7 940 6 9 444 6 11 809 7 8 786 9 10 468 7 10 234 6 10 660 4 12 939 8 10 896 1 11 953 8 10 818 4 8 967 3 9 724 6 7 929 3 4 948 1 3 999 10 11 724 7 10 338 1 8 967 1 12 733 581 978 950 629 583 729 554 712 438 930 774 279
输出 #3
2432 999 1672 2037 1762 1753 967 1723 1677 953 733
说明/提示
**样例 1 解释：**
例如，你可以按如下方式在 $7$ 分钟内从城市 $1$ 到达城市 $7$：
* 使用第一条道路，从城市 $1$ 到城市 $2$，耗时 $1$ 分钟。
* 使用传送门，从城市 $2$ 到城市 $7$，耗时 $1+2+3=6$ 分钟。
无法在 $6$ 分钟或更短时间内从城市 $1$ 到达城市 $7$，因此当 $k=7$ 时，答案为 $7$。
**样例 2 解释：**
注意，答案可能达到 $2 ^ {31}$ 或更大。
### 约束条件
* $2\le N\le2\times10 ^ 5$
* $0\le M\le2\times10 ^ 5$
* $1\le u _ i\lt v _ i\le N\ (1\le i\le M)$
* $1\le T _ i\le10 ^ 9\ (1\le i\le M)$
* $1\le X _ i\le10 ^ 9\ (1\le i\le N)$
* $1\le Y\le 10 ^ 9$
* 所有输入值均为整数。
例如，你可以按如下方式在 $7$ 分钟内从城市 $1$ 到达城市 $7$：
* 使用第一条道路，从城市 $1$ 到城市 $2$，耗时 $1$ 分钟。
* 使用传送门，从城市 $2$ 到城市 $7$，耗时 $1+2+3=6$ 分钟。
无法在 $6$ 分钟或更短时间内从城市 $1$ 到达城市 $7$，因此当 $k=7$ 时，答案为 $7$。
**样例 2 解释：**
注意，答案可能达到 $2 ^ {31}$ 或更大。
### 约束条件
* $2\le N\le2\times10 ^ 5$
* $0\le M\le2\times10 ^ 5$
* $1\le u _ i\lt v _ i\le N\ (1\le i\le M)$
* $1\le T _ i\le10 ^ 9\ (1\le i\le M)$
* $1\le X _ i\le10 ^ 9\ (1\le i\le N)$
* $1\le Y\le 10 ^ 9$
* 所有输入值均为整数。