No.1283 Extra Fee
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もしくは右上の雲マークをクリックしてアカウントを作成してください。
platinum
nok0