問題一覧 > 通常問題

No.2764 Warp Drive Spacecraft

レベル : / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 28
作問者 : 👑 binapbinap / テスター : maguroflymagurofly aplysiaSheepaplysiaSheep
0 ProblemId : 10881 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2024-05-29 11:20:54

問題文

binap銀河は惑星 $1$ から惑星 $N$ の $N$ 個の惑星で構成されます。今あなたは惑星 $1$ にいて $1$ 枚のワープチケットを持っています。惑星 $N$ にたどり着くのにかかる時間の最小値を求めてください。

binap銀河で惑星間を移動する方法は以下の $2$ 通りです。

・航路に沿った移動

$M$ 本の航路が規定されています。航路 $i$ は惑星 $U_i$と惑星 $V_i$ を双方向に繋いでおり時間 $T_i$ で行き来できます。

・ワープ航法による移動

各惑星は歪み度という値をもちます。惑星 $i$ ( $1 \leq i \leq N$ ) の歪み度は $W_i$です。任意の惑星 $i$ にいるとき、ワープチケットを $1$ 枚消費することで任意の惑星 $j$ へ歪み度の積 $W_iW_j$ の時間で移動できます。

入力

$N$ $M$
$W_1$ $W_2$ $\ldots$ $W_N$
$U_1$ $V_1$ $T_1$
$U_2$ $V_2$ $T_2$
$\vdots$
$U_M$ $V_M$ $T_M$
  • $2 \leq N \leq 2 \times 10^5$
  • $0 \leq M \leq 2 \times 10^5$
  • $1 \leq W_i \leq 10^9$ ( $1 \leq i \leq N$ )
  • $1 \leq U_i < V_i \leq N$ ( $1 \leq i \leq M$ )
  • $(U_i, V_i) = (U_j, V_j) \iff i = j$
  • $1 \leq T_i \leq 10^{12}$ ( $1 \leq i \leq M$ )
  • 入力はすべて整数

出力

答えを整数で出力してください。

最後に改行してください。

サンプル

サンプル1
入力
3 2
4 2 2
1 2 3
1 3 9
出力
7

上図は航路を黒色の辺、ワープ航法を青色の辺で表した図です。

惑星 $1$ から惑星 $2$ へ航路に沿って移動し、惑星 $2$ から $3$ へワープ航法で移動するのが最適です。

ワープ航法は $1$ 回しかできないことにも注意してください。

サンプル2
入力
3 3
314 159 265
1 2 1
2 3 2
1 3 4
出力
3

航路に沿った移動のみをするのが最適です。

サンプル3
入力
13 15
67 66 182 81 97 121 200 94 199 25 99 12 171
8 13 172
4 13 579
6 9 53
1 3 369
1 8 1367
2 6 1202
5 8 145
2 8 77
11 12 361
5 7 70
10 13 104
11 13 1411
1 11 115
6 11 63
4 10 222
出力
880

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。