A7689 | $Roads and Gates$

时间限制2s

内存限制1024MB

通过 / 提交0/0

题目描述

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$ 所需的最少时间。 在同一座城市内，由道路切换至另一条道路或传送门、或由传送门切换至另一条道路或传送门，所需换乘时间可忽略不计。

输入格式

输入从标准输入中按以下格式给出： > $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

C++ 编辑器

输入

输出

A7689 | Roads and Gates

题目描述

输入格式

输出格式

输入输出样例

A7689 | $Roads and Gates$