No.2764 Warp Drive Spacecraft
レベル : / 実行時間制限 : 1ケース 3.000秒 / メモリ制限
: 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 32
作問者 : 👑
binap
/ テスター :
magurofly
aplysiaSheep
タグ : / 解いたユーザー数 32
作問者 : 👑
![aplysiaSheep](https://pbs.twimg.com/profile_images/1755875215937265664/DA7ZDzYk.jpg)
問題文最終更新日: 2024-05-29 11:20:54
問題文
binap銀河は惑星 から惑星 の 個の惑星で構成されます。今あなたは惑星 にいて 枚のワープチケットを持っています。惑星 にたどり着くのにかかる時間の最小値を求めてください。
binap銀河で惑星間を移動する方法は以下の 通りです。
・航路に沿った移動
本の航路が規定されています。航路 は惑星 と惑星 を双方向に繋いでおり時間 で行き来できます。
・ワープ航法による移動
各惑星は歪み度という値をもちます。惑星 ( ) の歪み度は です。任意の惑星 にいるとき、ワープチケットを 枚消費することで任意の惑星 へ歪み度の積 の時間で移動できます。
入力
- ( )
- ( )
- ( )
- 入力はすべて整数
出力
答えを整数で出力してください。
最後に改行してください。
サンプル
サンプル1
入力
3 2 4 2 2 1 2 3 1 3 9
出力
7
上図は航路を黒色の辺、ワープ航法を青色の辺で表した図です。
惑星 から惑星 へ航路に沿って移動し、惑星 から へワープ航法で移動するのが最適です。
ワープ航法は 回しかできないことにも注意してください。
サンプル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もしくは右上の雲マークをクリックしてアカウントを作成してください。