AT_abc463_e.Roads and Gates

入门

通过率：0%

时间限制：2.00s

内存限制：1024MB

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

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

说明/提示

样例 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$
所有输入值均为整数。

输入解题思路，AI测评打分。不知道怎么写?

首页