問題一覧 > 通常問題

No.1283 Extra Fee

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 103
作問者 : platinumplatinum / テスター : nok0nok0
4 ProblemId : 5127 / 出題時の順位表
問題文最終更新日: 2020-10-05 12:50:51

問題文

Pythonをお使いの場合は、PyPyでの提出もご検討ください。


$N$ 行 $N$ 列のマス目があります。上から $h$ 行目、左から $w$ 列目のマスを、マス $(h,w)$ と呼びます。

はじめA君はマス $(1,1)$ にいます。A君はマス $(N,N)$ を目指して移動します。

A君は現在いるマスの上下左右いずれかのマスに移動でき、この時移動料金が $1$ かかります。

B君はマス $(1,1)$ とマス $(N,N)$ 以外のマスから $M$ 個マスを選び、A君がマス $(h_i,w_i)$ に到達した際に

通行料金 $c_i$ を徴収することにしました。B君が選択しなかったマスに通行料金は発生しません。

しかしこれに納得できないA君はB君と交渉し、好きな時に一度だけ通行料金を支払わなくても良いことになりました。

A君がマス $(N,N)$ に移動するまでにかかる、移動料金と通行料金の総和の最小値を求めてください。

入力

$N\ M$
$h_1\ w_1\ c_1$
$h_2\ w_2\ c_2$
$\vdots$
$h_M\ w_M\ c_M$

・入力は全て整数である。
・$2 \le N \le 500$
・$1 \le M \le N^2-2$
・$1 \le h_i,w_i \le N$
・$1 \le c_i \le 10^9$
・$(h_i,w_i) \neq (1,1),(N,N)$
・$h_i=h_j$ かつ $w_i=w_j$ なる $i,j$ $(i \neq j)$ は存在しない。

出力

A君がマス $(N,N)$ に移動するまでにかかる、移動料金と通行料金の総和の最小値を出力してください。

サンプル

サンプル1
入力
3 7
1 2 5
1 3 8
2 1 7
2 2 3
2 3 9
3 1 11
3 2 2
出力
9

マス $(1,1)$ → $(1,2)$ → $(2,2)$ → $(3,2)$ → $(3,3)$ と移動し、マス $(1,2$) の料金を支払わないのが最適です。
最終的な料金は、$($移動料金 $4$) $+$ $($通行料金 $5$) $=9$ となります。

サンプル2
入力
3 2
2 2 100
2 3 200
出力
4

この場合、そもそも通行料金がかかるマスを通過する必要がありません。

サンプル3
入力
5 22
3 5 6949
3 3 7763
2 3 6013
2 2 9260
5 3 111
1 4 2477
1 2 1349
5 4 7141
2 4 4843
5 1 6378
1 5 8295
3 4 326
4 5 6162
3 2 9381
3 1 182
4 4 7878
2 1 8440
2 5 4872
4 2 8346
4 3 2296
4 1 3398
5 2 6
出力
15165

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