Overview

On an \(H \times W\) grid, each time you enter a cell, you must pay that cell’s cost \(A_{i,j}\). The problem asks for the minimum cost to move from \((1,1)\) to \((H,W)\). Since this is a “shortest path problem on a vertex-weighted graph”, it can be solved using Dijkstra’s algorithm.

Analysis

Key Observation 1: This is a Graph Shortest Path Problem

Consider a graph where each cell is a vertex, and adjacent cells (up, down, left, right) are connected by edges. Then, “moving from \((1,1)\) to \((H,W)\)” corresponds to a path in this graph, and the total toll paid is the “sum of the weights of the visited vertices (excluding the starting cell \((1,1)\) initially)”.

Although the costs are associated with vertices rather than edges, we can easily convert them into edge costs:

Set the cost of the directed edge from vertex \(u\) to vertex \(v\) to \(A_v\) (the toll of the destination cell).

This naturally models the condition of “paying \(A_v\) each time you enter”. Since there is no cost for initially being at \((1,1)\), we can initialize the distance to the starting vertex as \(0\), and the answer will be the shortest distance to \((H,W)\).

Key Observation 2: Movement in All Four Directions Prevents a Simple DP Solution

If the movement were restricted to only “right” and “down”, it could be solved with a simple DP in \(O(HW)\): $\(dp[i][j] = \min(dp[i-1][j], dp[i][j-1]) + A_{i,j}\)$ However, in this problem, we can also move up and left, so there is no valid topological order for DP.

For example, consider the following case (\(H=3, W=3\)):

0 100 100
0   0 100
0   0   0

Here, moving “down, down, right, right” is optimal, and DP would work for paths moving monotonically towards the bottom-right. In general, however, we can have cases like:

0   0 100   0
100 100 100 0
0   0   0   0

where it is cheaper to detour or temporarily bypass and circle back. To handle movement in all four directions (up, down, left, right), we need a shortest path algorithm that does not rely on a fixed evaluation order.

Key Observation 3: Dijkstra’s Algorithm (Not BFS, No Negative Edges)

Since the costs are not uniformly \(1\), simple BFS cannot be used. On the other hand, because \(A_{i,j} \ge 0\), all edge costs are non-negative, allowing us to directly apply Dijkstra’s algorithm (we do not need algorithms like Bellman-Ford since there are no negative edges).

The number of vertices in the grid is \(HW \le 2 \times 10^5\), and the number of edges is roughly \(4\) times that, so Dijkstra’s algorithm using a priority queue is sufficiently fast.

Algorithm

1. Assign vertex index \(i \times W + j\) to cell \((i,j)\) (0-indexed), and maintain distances in a 1D array dist.
2. Set dist[(0,0)] = 0, and push \((0, \text{start})\) into a priority queue (min-heap).
3. Pop the vertex \(v\) with the minimum distance from the queue. If the extracted distance \(d\) is greater than dist[v], it is outdated information, so skip it (lazy deletion).
4. For each of the four neighboring cells \((ni,nj)\) (up, down, left, right) of \(v = (i,j)\), if \((ni,nj)\) is within the grid, compute $\(nd = d + A_{ni,nj}\)$ and if nd < dist[(ni,nj)], update the distance and push it into the queue.
5. Terminate when the queue becomes empty or when \((H-1, W-1)\) is popped. dist[(H-1,W-1)] is the answer.

By the properties of Dijkstra’s algorithm, the shortest distance to the destination is finalized the moment it is popped from the queue, so we can terminate early at that point (which serves as an optimization).

Complexity

Let \(V = HW\) be the number of vertices and \(E \le 4HW\) be the number of edges:

• Time Complexity: \(O(HW \log(HW))\)
• Space Complexity: \(O(HW)\)

Since \(HW \le 2 \times 10^5\), this will comfortably pass within the time limit.

Implementation Details

• Beware of overflow: Since \(A_{i,j} \le 10^9\) and the path length can be up to around \(HW = 2 \times 10^5\), the total distance can reach the scale of \(10^9 \times 2 \times 10^5 = 2 \times 10^{14}\). This will overflow a 32-bit integer, so use a 64-bit integer like long long (not an issue in Python).

• Setting INF: Using LLONG_MAX directly can cause an overflow when adding edge weights, so use a sufficiently large value with enough headroom, such as LLONG_MAX / 4.

• 2D to 1D conversion: Because \(H\) and \(W\) individually can be up to \(10^5\), a fixed-size 2D array cannot be used. It is straightforward to flatten the grid and store distances in a 1D array using id(i,j) = i * W + j.

• Lazy deletion: Since std::priority_queue does not support updating keys, use the standard pattern of pushing a new pair whenever an update occurs and ignoring popped entries if d > dist[v].

• Do not add the starting cell’s cost initially: The key is to start with dist[(0,0)] = 0 (\(A_{1,1}\) is not paid at the beginning). If the path ever revisits \((1,1)\), \(A_{1,1}\) will naturally be added as an edge cost, so no special handling is required.

• Fast I/O: Since there are up to \(2 \times 10^5\) integer inputs, it is recommended in C++ to use fast I/O such as scanf or std::cin with std::ios::sync_with_stdio(false).

  Source Code

#include <bits/stdc++.h>
using namespace std;

int main(){
    int H, W;
    if(scanf("%d %d", &H, &W) != 2) return 0;
    vector<vector<long long>> A(H, vector<long long>(W));
    for(int i = 0; i < H; i++)
        for(int j = 0; j < W; j++){
            long long x; scanf("%lld", &x); A[i][j] = x;
        }
    const long long INF = LLONG_MAX / 4;
    vector<long long> dist((size_t)H * W, INF);
    auto id = [&](int i, int j){ return (size_t)i * W + j; };
    using P = pair<long long, int>;
    priority_queue<P, vector<P>, greater<P>> pq;
    dist[id(0,0)] = 0;
    pq.push({0, 0});
    int di[4] = {-1, 1, 0, 0};
    int dj[4] = {0, 0, -1, 1};
    while(!pq.empty()){
        auto [d, v] = pq.top(); pq.pop();
        if(d > dist[v]) continue;
        int i = v / W, j = v % W;
        if(i == H-1 && j == W-1) break;
        for(int k = 0; k < 4; k++){
            int ni = i + di[k], nj = j + dj[k];
            if(ni < 0 || ni >= H || nj < 0 || nj >= W) continue;
            long long nd = d + A[ni][nj];
            size_t u = id(ni, nj);
            if(nd < dist[u]){
                dist[u] = nd;
                pq.push({nd, (int)u});
            }
        }
    }
    printf("%lld\n", dist[id(H-1, W-1)]);
    return 0;
}

---

This editorial was generated by claude5opus-high.