No.496 ワープクリスタル (給料日前編)

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 101
作問者 : TawaraTawara / テスター : 37zigen37zigen

3 ProblemId : 934 / 出題時の順位表

問題文

Crystal City は、瞬時に別の場所に移動できるワープクリスタルが使えることで有名な街です。
ただ任意の位置に移動できるわけではなく、クリスタルごとに現在地から移動できる相対位置が決まっています。

  • Crystal City は正方形の区画を敷き詰めてできている街です。
    各区画は整数座標 $(x,y)$ で表現され、東と北が それぞれ$x$ 軸、$y$ 軸の正の向きに対応します。
  • 各ワープクリスタルには移動できる相対位置 $(x,y)$($x,y$ は整数)が記されており、
    区画 $(X_1,Y_1)$ で使うと区画 $(X_1+x,Y_1+y)$ にワープ出来ます。
  • ある区画から徒歩で移動できるのは隣接する東西南北のいずれかの区画です。
    その際一律の通行料を払う必要があります。
区画 $(0,0)$ に住むクリス君は今から区画 $(G_x,G_y)$ ($G_x,G_y \ge 0$) に出かけようとしています。
給料日前のクリス君は、目的地に着くまでに使うクリスタルの値段と支払う通行料の合計をできるだけ節約したいと考えています。
計算が苦手なクリス君に代わって、目的地までたどり着く最小のコストを計算してください。

ただし今日のクリス君は目的地に対して後退するような移動を嫌がっているようです。
なので、現在地から西や南の方向にある区画への移動は行わないものとして計算してください。

22:48 追記 クリスタルは一度使ったら無くなります。

入力

$G_x \ G_y \ N \ F\\
x_1 \ y_1 \  c_1 \\
. \\
. \\
x_N \ y_N \ c_N
$

入力は空白区切りで与えられます。
1行目には目的地の区画の座標 $(G_x, G_y)$、クリス君が所持するクリスタルの数 $N$、隣接する区画へ徒歩で移動するときの通行料 $F$ が与えられます。
2行目から$N+1$行目には各クリスタルの移動できる相対位置 $(x_i,y_i)$と値段 $c_i$ が与えられます。

入力は全て整数であり、以下の制約を満たします。
$ 0 \le Gx,Gy \le 100$
$ 0 \le N \le 50 $
$ 1 \le F \le 200 $
$0 \le x_i \le Gx$, $0 \le y_i \le Gy$, $ (x_i, y_i) \neq (0,0) $
$1 \le c_i \le 200 $

制約からもわかりますが、今日のクリス君は西や南へ移動するクリスタルを使いません。
問題文で述べたように西や南の区画に徒歩で移動することもありません。

出力

クリス君が $(0,0)$ から $(Gx,Gy)$ へたどり着く最小コストを出力して下さい。 最後に改行してください。

サンプル

サンプル1
入力
3 3 2 1
1 2 2
2 1 2
出力
4

例えば以下のように、クリスタルのみを使って移動するとコストが最小です。

サンプル2
入力
3 3 2 1
1 2 2
2 1 4
出力
5

2個目のクリスタルを使うよりも、歩く方がコストが少なく済みます。

サンプル3
入力
5 3 5 2
5 0 6
5 0 6
2 2 6
0 2 3
3 1 6
出力
11

3個目と5個目のクリスタルを使うと歩かずに目的地につけますが、その場合のコストは12なので最小ではありません。
また、全く同一のクリスタルが複数あることもあります。

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

通行料が安いので頑張って歩くことにしました。

提出ページヘ