概要

\(H \times W\) のグリッド上をマス \((1, 1)\) からマス \((H, W)\) まで上下左右に移動するとき、通過するマスの通行料の合計を最小化する問題です。

考察

素朴なアプローチとその問題点

グリッドの左上から右下への移動と聞くと、動的計画法（DP）を思い浮かべるかもしれません。しかし、この問題では「右と下」だけでなく「上下左右」の \(4\) 方向に移動できます。 例えば、目の前のマスの通行料が非常に高い場合、少し遠回りをして安いマスを迂回したほうが全体のコストが小さくなることがあります。上下左右に移動できるということは経路にループや逆走が含まれ得るため、遷移の順序を一方向に決められず、通常のDPでは解くことができません。

最短経路問題への帰着

通行料 \(A_{i, j}\) はすべて \(0\) 以上の非負整数です。この性質から、この問題は「負のコストを持たないグラフにおける単一始点最短経路問題」として捉えることができます。

• 頂点: 各区画 \((i, j)\) （合計 \(H \times W\) 個）
• 辺: 上下左右に隣接するマスへの移動
• 辺の重み: 移動先の区画 \((r, c)\) の通行料 \(A_{r, c}\)

問題の条件より、最初のマス \((1, 1)\) にいる時点では通行料を支払いませんが、目的地のマス \((H, W)\) に入る際には通行料を支払います。これは、辺 \((u, v)\) の重みを「移動先の頂点 \(v\) の通行料 \(A_v\)」と設定することで自然に表現できます。 辺の重みがすべて非負であるため、ダイクストラ法（Dijkstra’s Algorithm） を用いることで効率的に最小コストを求めることができます。

アルゴリズム

優先度付きキュー（ヒープ）を用いたダイクストラ法を使用します。

1. マスの 1 次元化: マス \((r, c)\)（\(0\)-indexed）を一意な整数 \(u = r \times W + c\) で表すことで、グラフの頂点番号を \(0\) から \(H \times W - 1\) の 1 つの整数として扱います。
2. 初期化:
   • 各頂点への暫定最短距離を記録する配列 dist を用意し、すべて十分に大きな値（\(\infty\)）で初期化します。
   • 始点 \((0, 0)\)（マス \((1, 1)\)）の距離を dist[0] = 0 とします。
   • 優先度付きキューに (距離, 頂点番号) = (0, 0) を追加します。
3. 探索:
   • キューから最も距離が小さい頂点 \(u\) を取り出します。
   • すでに記録されている最短距離より大きい場合はスキップします。
   • 目的地 \(u = H \times W - 1\)（マス \((H, W)\)）が取り出された時点で、目的地への最短距離が確定しているため探索を打ち切ることができます。
   • 頂点 \(u\) から上下左右に隣接する有効なマス \(v\) を調べます。
   • dist[u] + A[v] < dist[v] である場合、dist[v] を更新し、キューに (dist[v], v) を追加します。
4. 答えの出力: 最終的な dist[H * W - 1] の値を出力します。

計算量

頂点数を \(V = H \times W\)、辺数を \(E\) とします。各頂点から隣接する頂点への移動は上下左右の高々 \(4\) 方向であるため、辺数は \(E \le 4V\) です。

• 時間計算量: \(O((V + E) \log V) = O((HW) \log (HW))\) 制約より \(HW \le 2 \times 10^5\) であるため、計算ステップ数は高々 \(2 \times 10^5 \times \log_2(2 \times 10^5) \approx 3.6 \times 10^6\) 程度となり、実行時間制限に余裕で間に合います。
• 空間計算量: \(O(HW)\) グリッド情報、最短距離配列 dist、優先度付きキューで保持するデータ量は頂点数に比例します。

実装のポイント

• オーバーフローへの配慮: 通行料の合計は最大で \(HW \times 10^9 \approx 2 \times 10^{14}\) に達する可能性があります。これは 32 bit 符号付き整数の上限（約 \(2 \times 10^9\)）を超えるため、通行料や距離配列には 64 bit 整数型（C++の long long）を使用する必要があります。これに伴い、初期値の \(\infty\) も \(10^{18}\) などの十分大きい値を設定してください。

• メモリ制約の回避: \(H, W \le 10^5\) かつ \(H \times W \le 2 \times 10^5\) という制約です。固定長配列などでサイズ \(10^5 \times 10^5\) を確保しようとするとメモリ制限（MLE）になります。\(1\) 次元配列（サイズ \(H \times W\)）として確保するか、動的配列を活用してください。

  ソースコード

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int H, W;
    if (!(cin >> H >> W)) return 0;

    vector<long long> A(H * W);
    for (int i = 0; i < H * W; ++i) {
        cin >> A[i];
    }

    const long long INF = 1e18;
    vector<long long> dist(H * W, INF);
    priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> pq;

    dist[0] = 0;
    pq.emplace(0, 0);

    int dr[] = {-1, 1, 0, 0};
    int dc[] = {0, 0, -1, 1};

    while (!pq.empty()) {
        auto [d, u] = pq.top();
        pq.pop();

        if (d > dist[u]) continue;
        if (u == H * W - 1) break;

        int r = u / W;
        int c = u % W;

        for (int i = 0; i < 4; ++i) {
            int nr = r + dr[i];
            int nc = c + dc[i];

            if (nr >= 0 && nr < H && nc >= 0 && nc < W) {
                int v = nr * W + nc;
                if (dist[u] + A[v] < dist[v]) {
                    dist[v] = dist[u] + A[v];
                    pq.emplace(dist[v], v);
                }
            }
        }
    }

    cout << dist[H * W - 1] << "\n";

    return 0;
}

---

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