問題一覧 > 通常問題

No.1283 Extra Fee

レベル : / AI推定難易度 : 1175 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 153
作問者 : platinum / テスター : nok0
お気に入りにしたユーザー ProblemId : 5127 / 自分の提出
問題文最終更新日: 2020-10-05 12:50:51
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 273 (順位表) の他の問題:

Problem Statement

If you are using Python, please also consider submitting with PyPy.


There is a grid with $N$ rows and $N$ columns. The square in the $h$-th row from the top and the $w$-th column from the left is called square $(h,w)$.

Initially, A is at square $(1,1)$. A moves with the goal of reaching square $(N,N)$.

A can move to the square directly above, below, left of, or right of the current square, and each such move costs a movement fee of $1$.

B has chosen $M$ squares from the squares other than square $(1,1)$ and square $(N,N)$, and has decided that when A reaches square $(h_i,w_i)$,

a toll of $c_i$ is collected. No toll is charged on squares that B did not choose.

However, A was not satisfied with this and negotiated with B, and it was agreed that A may skip paying a toll once, at any time A likes.

Find the minimum possible total of the movement fees and tolls that A pays until moving to square $(N,N)$.

Input

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

・All inputs are integers.
・$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)$
・There is no pair $i,j$ $(i \neq j)$ such that $h_i=h_j$ and $w_i=w_j$.

Output

Output the minimum possible total of the movement fees and tolls that A pays until moving to square $(N,N)$.

Sample

Sample 1
Input
3 7
1 2 5
1 3 8
2 1 7
2 2 3
2 3 9
3 1 11
3 2 2
Output
9

It is optimal to move along squares $(1,1)$ → $(1,2)$ → $(2,2)$ → $(3,2)$ → $(3,3)$ and not pay the toll of square $(1,2$).
The final cost is $($movement fee $4$) $+$ $($toll $5$) $=9$.

Sample 2
Input
3 2
2 2 100
2 3 200
Output
4

In this case, there is no need to pass through any square with a toll in the first place.

Sample 3
Input
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
Output
15165

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