問題一覧 > 通常問題

No.2764 Warp Drive Spacecraft

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

問題文

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

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

・航路に沿った移動

MM 本の航路が規定されています。航路 ii は惑星 UiU_iと惑星 ViV_i を双方向に繋いでおり時間 TiT_i で行き来できます。

・ワープ航法による移動

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

入力

NN MM
W1W_1 W2W_2 \ldots WNW_N
U1U_1 V1V_1 T1T_1
U2U_2 V2V_2 T2T_2
\vdots
UMU_M VMV_M TMT_M
  • 2N2×1052 \leq N \leq 2 \times 10^5
  • 0M2×1050 \leq M \leq 2 \times 10^5
  • 1Wi1091 \leq W_i \leq 10^9 ( 1iN1 \leq i \leq N )
  • 1Ui<ViN1 \leq U_i < V_i \leq N ( 1iM1 \leq i \leq M )
  • (Ui,Vi)=(Uj,Vj)    i=j(U_i, V_i) = (U_j, V_j) \iff i = j
  • 1Ti10121 \leq T_i \leq 10^{12} ( 1iM1 \leq i \leq M )
  • 入力はすべて整数

出力

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

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

サンプル

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

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

惑星 11 から惑星 22 へ航路に沿って移動し、惑星 22 から 33 へワープ航法で移動するのが最適です。

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

サンプル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もしくは右上の雲マークをクリックしてアカウントを作成してください。