Overview

This problem asks us to minimize the total toll of the visited cells when moving from cell \((1, 1)\) to cell \((H, W)\) on an \(H \times W\) grid, moving up, down, left, and right.

Analysis

Naive Approach and Its Issues

When hearing about moving from the top-left to the bottom-right of a grid, one might think of dynamic programming (DP). However, in this problem, we can move in all \(4\) directions—up, down, left, and right—not just “right and down”. For example, if the toll of the cell right in front of us is extremely high, taking a detour through cheaper cells may result in a smaller overall cost. Since we can move in all four directions, the path could contain loops or backtracking, which means the order of transitions cannot be determined in a single direction. Therefore, standard DP cannot be used to solve this problem.

Reduction to the Shortest Path Problem

All tolls \(A_{i, j}\) are non-negative integers (\(\ge 0\)). From this property, this problem can be formulated as a “single-source shortest path problem on a graph with non-negative edge weights”.

• Vertices: Each cell \((i, j)\) (a total of \(H \times W\) vertices)
• Edges: Moves to vertically or horizontally adjacent cells
• Edge weights: The toll \(A_{r, c}\) of the destination cell \((r, c)\)

According to the problem statement, we do not pay the toll when starting at cell \((1, 1)\), but we do pay the toll when entering the destination cell \((H, W)\). This can be naturally represented by setting the weight of each directed edge \((u, v)\) to “the toll \(A_v\) of the destination vertex \(v\)”. Since all edge weights are non-negative, we can efficiently find the minimum cost using Dijkstra’s Algorithm.

Algorithm

We use Dijkstra’s algorithm with a priority queue (heap).

1. Flattening the 2D Grid to 1D: Represent each cell \((r, c)\) (\(0\)-indexed) as a unique integer \(u = r \times W + c\), treating the graph’s vertices as single integers from \(0\) to \(H \times W - 1\).
2. Initialization:
   • Create an array dist to store the tentative shortest distance to each vertex, initialized to a sufficiently large value (\(\infty\)).
   • Set the distance to the starting vertex \((0, 0)\) (cell \((1, 1)\)) to dist[0] = 0.
   • Push (distance, vertex) = (0, 0) into the priority queue.
3. Search:
   • Pop the vertex \(u\) with the minimum distance from the priority queue.
   • If the popped distance is greater than the currently recorded shortest distance, skip it.
   • When the destination \(u = H \times W - 1\) (cell \((H, W)\)) is popped, its shortest distance is finalized, so we can terminate the search early.
   • Check all valid adjacent cells \(v\) (up, down, left, right) from vertex \(u\).
   • If dist[u] + A[v] < dist[v], update dist[v] and push (dist[v], v) into the priority queue.
4. Output the Answer: Output the final value of dist[H * W - 1].

Complexity

Let \(V = H \times W\) be the number of vertices and \(E\) be the number of edges. Since each vertex can transition to at most \(4\) adjacent directions (up, down, left, right), the number of edges satisfies \(E \le 4V\).

• Time Complexity: \(O((V + E) \log V) = O((HW) \log (HW))\) Given the constraint \(HW \le 2 \times 10^5\), the number of operations is at most around \(2 \times 10^5 \times \log_2(2 \times 10^5) \approx 3.6 \times 10^6\), which easily runs well within the time limit.
• Space Complexity: \(O(HW)\) The memory required for the grid information, the shortest distance array dist, and the priority queue is proportional to the number of vertices.

Implementation Notes

• Handling Integer Overflow: The total toll can reach up to \(HW \times 10^9 \approx 2 \times 10^{14}\). This exceeds the limit of a 32-bit signed integer (approximately \(2 \times 10^9\)), so 64-bit integer types (long long in C++) must be used for the tolls and the distance array. Accordingly, initialize \(\infty\) to a sufficiently large value such as \(10^{18}\).

• Avoiding Memory Limit Exceeded (MLE): The constraints are \(H, W \le 10^5\) and \(H \times W \le 2 \times 10^5\). Trying to allocate a static 2D array of size \(10^5 \times 10^5\) will result in Memory Limit Exceeded (MLE). Either allocate a \(1\)D array of size \(H \times W\) or use dynamic arrays.

  Source Code

#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;
}

---

This editorial was generated by gemini-3.8-flash-high.