問題3: ダイクストラ法 - 経路復元 (hard)
(paizaランク A 相当)
問題にチャレンジして、ユーザー同士で解答を教え合ったり、コードを公開してみよう！
シェア用URL:
ツイートする
問題
下記の問題をプログラミングしてみよう！
この問題は前問 (問題3: ダイクストラ法 - 経路復元) の制約強化版です。
グリッド状の盤面で上下左右の移動を繰り返して、プレイヤーが左上のスタートから右下のゴールまで移動するときに通るマス (スタート、ゴール含む) のコストの合計の最小値を求めてください。
さらに対応する経路をゴールからスタートまでの順序で出力してください。なお、コストが最小になるような経路は複数存在する可能性がありますが、その場合はどの経路を出力しても正答となります。
※この問題は、paiza開発日誌で詳しく解説しています
- 入力される値
-
h w
t_{0,0} t_{0,1} ... t_{0,w-1}
t_{1,0} t_{1,1} ... t_{1,w-1}
...
t_{h-1,0} t_{h-1,1} ... t_{h-1,w-1}
・ 1 行目には盤面の行数を表す h , 盤面の列数を表す w が与えられます。
・ 続く h 行のうち i 行目には、i 行目のマスのコストを表す整数値のリスト t_i が与えられます。
・ t_{i,j} は i 行目の j 列目のコストです。
入力値最終行の末尾に改行が１つ入ります。
文字列は標準入力から渡されます。 標準入力からの値取得方法はこちらをご確認ください
- 期待する出力
コストの合計の最小値を 1 行目に出力してください。
続けて、ゴールからスタートまでの経路を以下のようにマスの並びとして出力してください。y_1 x_1
y_2 x_2
...
y_n x_n
・ n は最短経路上のマスの数です。
・ (y_t, x_t) は、プレイヤーが上から y_t 行目、左から x_t 列目にいることを表しています。
・ (y_1, x_1) = (h-1, w-1), (y_n, x_n) = (0, 0) を満たしている必要があります。
・ コストが最小ではない・経路が不正 の場合は不正解となります。
- 条件
-
すべてのテストケースにおいて、以下の条件をみたします。
・ 1 ≦ h , w ≦ 100
・ 0 ≦ t_{i,j} ≦ 100 (0 ≦ i < h, 0 ≦ j < w)
- 入力例1
-
3 6
0 3 1 4 1 5
9 2 6 5 3 5
3 9 7 9 3 2
- 出力例1
-
17
2 5
2 4
1 4
0 4
0 3
0 2
0 1
0 0
