概要

\(H \times W\) のグリッド上で、マス \((r,c)\) に入るたびにコスト \(A_{r,c}\) を支払うとき、\((1,1)\) から \((H,W)\) へ移動する最小コストを求める問題です。これは「頂点に重みがあるグリッドグラフの最短経路問題」であり、ダイクストラ法で解けます。

考察

重要な気づき 1: これはグラフの最短経路問題

各マスを頂点とし、上下左右に隣接するマス同士を辺で結んだグラフを考えます。すると「高橋君の移動」はこのグラフ上の歩道（walk）に対応し、支払う総額は「通ったマス（ただし出発時の \((1,1)\) は除く）の \(A\) の総和」になります。

コストが「マスに入るとき」に発生するので、辺 \(u \to v\) の重みを \(A_v\)（移動先のマスの通行料） と定めれば、\((1,1)\) から \((H,W)\) への最短路長がそのまま答えになります。始点にいるだけでは料金がかからないので、\(\mathrm{dist}[(1,1)] = 0\) とすればよく、\(A_{1,1}\) は答えに含まれません（ただし一度出て戻ってきたら \(A_{1,1}\) を払う、という挙動もこの辺重みの定義で自動的に表現されています）。

重要な気づき 2: 単純な右・下方向の DP では解けない

グリッドの経路問題でよくある「右か下にしか動けない」タイプなら \(O(HW)\) の DP で解けますが、本問では 上下左右すべてに動けるため、DP の計算順序が定まりません。

例えば次のようなケースを考えます。

0 100 100
0 100 100
0   0   0

\((1,1) \to (2,1) \to (3,1) \to (3,2) \to (3,3)\) と進めば合計 \(0\) 円ですが、これは「下・下・右・右」で右下方向のみなので DP でも扱えます。しかし一般には、いったん上や左に戻った方が安い場合があります。

5 1 1 1 1
5 5 5 5 1
1 1 1 1 1   ← 例えばこのように「回り込み」が最適になる形が作れる

上下左右すべての移動を許すと、あるマスの最短距離が「まだ計算していない（右や下の）マス」に依存し得るため、単純な二重ループの DP は成立しません（WA になります）。

解決方法

移動の向きに制限がないグラフの最短経路なので、ダイクストラ法を使います。辺の重み \(A_{i,j}\) は \(0\) 以上なので負辺は存在せず、ダイクストラ法が正しく適用できます。

なお、重みが \(0\) の辺があってもダイクストラ法は問題なく動作します（負でなければよい）。また、辺重みは最大 \(10^9\)、経路長は最大でも \(O(HW)\) 程度のマス数なので合計は約 \(2\times 10^{14}\) になり、C++ 等では 64bit 整数を使う必要があります（Python は自動多倍長なので気にしなくて OK）。

アルゴリズム

1. マス \((i,j)\)（0-indexed）を頂点番号 \(i \times W + j\) に対応させ、1 次元配列で扱う。
2. \(\mathrm{dist}\) 配列を \(\infty\) で初期化し、\(\mathrm{dist}[0] = 0\) とする。
3. 優先度付きキュー（最小ヒープ）に \((0, 0)\) を入れる。
4. キューから距離最小の頂点 \(i\) を取り出す。取り出した距離 \(d\) が \(\mathrm{dist}[i]\) より大きければ古い情報なのでスキップ。
5. \(i\) の上下左右の隣接マス \(j\) について、\(d + A_j < \mathrm{dist}[j]\) なら更新してキューに push。
6. 頂点 \(N-1 = HW-1\)（つまり \((H,W)\)）を取り出した時点で、その距離が答え。

ダイクストラ法では「取り出した時点でその頂点の距離が確定している」ので、ゴールを取り出したら即座に答えを出力して終了できます（枝刈りとして有効）。

グラフのサイズは頂点数 \(N = HW \le 2\times 10^5\)、辺数は各頂点から最大 4 本なので \(O(HW)\) です。

計算量

• 時間計算量: \(O(HW \log (HW))\)
• 空間計算量: \(O(HW)\)

\(HW \le 2 \times 10^5\) なので十分高速です。

実装のポイント

• 2 次元配列を作らず 1 次元で持つ: \(H, W\) は片方が \(10^5\) になり得るため、A[i][j] のような二重リストよりも、入力を読んだトークン列をそのまま 1 次元配列として使う方がメモリ・速度の両面で有利です。インデックス \(i\) から座標は r, c = divmod(i, W) で復元でき、左右移動は i-1, i+1、上下移動は i-W, i+W です。

• 境界判定: 左右移動のときは c > 0 / c+1 < W を必ず確認します。1 次元化しているので、c == W-1 のときに i+1 とすると次の行の先頭に「ワープ」してしまうバグに注意してください（上下は i-W, i+W が範囲内かどうかだけで判定できます）。

• 入力の高速化: \(HW\) が最大 \(2\times 10^5\) 個の整数入力なので、Python では sys.stdin.buffer.read().split() で一括読み込みするのが安全です。

• 遅延削除型ダイクストラ: visited 配列を使わず、if d > dist[i]: continue で古いエントリを捨てる形にすると実装が短くなります。

• 辺の重みは「入る先」の値: nd = d + A[j]（\(j\) は移動先）とするのがポイントです。A[i]（現在地）を足してしまうと、\(A_{1,1}\) を払うことになったり \(A_{H,W}\) を払わないことになったりして答えがずれます。

  ソースコード

import sys
from heapq import heappush, heappop

def main():
    data = sys.stdin.buffer.read().split()
    H = int(data[0]); W = int(data[1])
    N = H * W
    A = [int(x) for x in data[2:2 + N]]
    INF = float('inf')
    dist = [INF] * N
    dist[0] = 0
    hq = [(0, 0)]
    goal = N - 1
    while hq:
        d, i = heappop(hq)
        if d > dist[i]:
            continue
        if i == goal:
            sys.stdout.write(str(d) + "\n")
            return
        r, c = divmod(i, W)
        if c > 0:
            j = i - 1
            nd = d + A[j]
            if nd < dist[j]:
                dist[j] = nd
                heappush(hq, (nd, j))
        if c + 1 < W:
            j = i + 1
            nd = d + A[j]
            if nd < dist[j]:
                dist[j] = nd
                heappush(hq, (nd, j))
        if r > 0:
            j = i - W
            nd = d + A[j]
            if nd < dist[j]:
                dist[j] = nd
                heappush(hq, (nd, j))
        if r + 1 < H:
            j = i + W
            nd = d + A[j]
            if nd < dist[j]:
                dist[j] = nd
                heappush(hq, (nd, j))
    sys.stdout.write(str(dist[goal]) + "\n")

main()

---

この解説は claude5opus-high によって生成されました。