問題一覧 > 通常問題

No.1449 新プロランド

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 63
作問者 : linuxmetellinuxmetel / テスター : shiomusubi496shiomusubi496
2 ProblemId : 6103 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2021-04-03 09:33:58

制約違反のケースが見つかりました。該当するケースを削除して、リジャッジをかけさせていただきました。 申し訳ございませんでした

問題文

しおむすび共和国には、町 $1$ から町 $N$ までの $N$ 個の町と、道路 $1$ から道路 $M$ までの $M$ 本の道路があります。道路 $i$ は $A_i$ と $B_i$ ($A_i < B_i$) を双方向に結んでいて、長さは $C_i$ です。

しおむすび共和国では、町 $i$ に着いてから町 $i$ を出発するまでに、しおむすびをちょうど $T_i$ 分間食べる必要があります。(町 $1$ を出発するときにもしおむすびを食べる必要がありますが、町 $N$ に到着した時に食べる必要はありません。)

同じ町を何度も通ることも可能で、そのたびにしおむすびを食べる必要があります。

また、町 $1$ を出発してからしおむすびを合計で $P$ 分間食べたとき、長さ $l$ の道路を $\lfloor \frac{l}{P} \rfloor$ 分で通ることができます。(制約下で $P=0$ で道を渡ることがないと証明できます。)

Liunxmetel 君は、自分が住む町 $1$ から、新プロランドがある町 $N$ におでかけに行こうと思っています。 Linuxmetel 君が、町 $N$ につくまでにかかる時間の最小値を求めなさい。

ただし、 Linuxmetel くんは道路以外を通って別の町に移動することはできません。また、町以外のところでしおむすびを食べることはありません。

入力

$N\ M$
$A_1\ B_1\ C_1$
$A_2\ B_2\ C_2$
  $\vdots$
$A_M\ B_M\ C_M$
$T_1\ T_2\ \ldots\ T_N$
  • 入力はすべて整数
  • $2 \leq N\leq 100$
  • $1 \leq M\leq\min\left(\frac{N(N-1)}{2},100\right)$
  • $1 \leq A_i < B_i \leq N$
  • $i \neq j$ ならば $(A_i, B_i) \neq (A_j, B_j)$
  • $1 \leq C_i \leq 1000$
  • $0 \leq T_i \leq 100$
  • $T_1 \neq 0,T_N = 0$
  • 与えられる入力データにおいては、町 $1$ から町 $N$ まで $0$ 個以上の町を通って移動できることが保証されている

出力

Linuxmetel 君が、町 $N$ につくまでにかかる時間の最小値を正整数で出力せよ。

また、最後に改行を出力せよ。

サンプル

サンプル1
入力
2 1
1 2 10
1 0
出力
11

例えば次のような移動ができます。

  1. 町 $1$ を出発する前にしおむすびを $1$ 分間食べる
  2. 道路 $1$ を使い、 $\lfloor\frac{10}{1}\rfloor=10$ 分間かけて町 $2$ に移動する

$10$ 分以下で町 $2$ に行く方法はないため、 $11$ を出力します。

サンプル2
入力
4 4
1 2 9
1 3 6
2 4 8
3 4 5
3 1 2 0
出力
8

例えば次のような移動ができます。

  1. 町 $1$ を出発する前にしおむすびを $3$ 分間食べる
  2. 道路 $2$ を使い、$\lfloor\frac{6}{3}\rfloor=2$ 分間かけて町 $3$ に移動する
  3. 町 $3$ を出発する前にしおむすびを $2$ 分間食べる
  4. 道路 $4$ を使い、$\lfloor\frac{5}{5}\rfloor=1$ 分間かけて町 $4$ に移動する

$7$ 分以下で町 $4$ に行く方法はないため、 $8$ を出力します。

サンプル3
入力
6 15
2 6 202
1 2 185
3 6 978
2 3 976
3 4 445
1 6 795
1 5 951
2 4 626
4 5 265
1 4 501
1 3 685
2 5 899
5 6 766
3 5 923
4 6 343
46 19 23 75 48 0
出力
63

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