Overview

On an \(H \times W\) grid, each time you enter cell \((r,c)\), you pay a cost of \(A_{r,c}\). The problem asks for the minimum cost to move from \((1,1)\) to \((H,W)\). This is a “shortest path problem on a grid graph with vertex weights” and 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 edges connect adjacent cells in the four cardinal directions (up, down, left, right). Then, Takahashi’s movement corresponds to a walk on this graph, and the total cost paid is the sum of \(A\) for all visited cells (excluding the starting cell \((1,1)\)).

Since the cost is incurred “upon entering a cell”, if we define the weight of an edge \(u \to v\) as \(A_v\) (the cost of the destination cell), the shortest path length from \((1,1)\) to \((H,W)\) directly gives the answer. Since simply being at the starting cell incurs no fee, we can set \(\mathrm{dist}[(1,1)] = 0\), and \(A_{1,1}\) is not included in the answer (furthermore, if Takahashi leaves and returns to \((1,1)\), paying \(A_{1,1}\) is also automatically captured by this definition of edge weights).

Key Observation 2: Cannot be Solved with Simple Right/Down DP

In typical grid path problems where one can only move right or down, it could be solved with an \(O(HW)\) DP. However, in this problem, we can move in all four directions (up, down, left, right), so the DP transition order is not determined.

For example, consider the following case:

0 100 100
0 100 100
0   0   0

Moving \((1,1) \to (2,1) \to (3,1) \to (3,2) \to (3,3)\) costs a total of \(0\). This path only goes down and right (“down, down, right, right”), which could be handled by DP. However, in general, it might be cheaper to detour upwards or to the left.

5 1 1 1 1
5 5 5 5 1
1 1 1 1 1   ← For example, a "detour" like this can be optimal

When moving in all four directions is allowed, the shortest distance to a cell can depend on cells that haven’t been computed yet (e.g., cells to the right or below), so a simple nested-loop DP will not work (resulting in WA).

Solution

Since this is a shortest path problem on a graph with no restrictions on movement direction, we can use Dijkstra’s algorithm. Because the edge weights \(A_{i,j}\) are all non-negative (\(0\) or greater), there are no negative edges, and Dijkstra’s algorithm can be applied correctly.

Note that Dijkstra’s algorithm works fine even with edges of weight \(0\) (as long as they are non-negative). In addition, since edge weights can be up to \(10^9\) and the path length can span up to \(O(HW)\) cells, the total sum can reach about \(2\times 10^{14}\). Therefore, languages like C++ require 64-bit integers (Python handles arbitrarily large integers automatically, so no special care is needed).

Algorithm

1. Map each cell \((i,j)\) (0-indexed) to vertex ID \(i \times W + j\), handling them in a 1D array.
2. Initialize the \(\mathrm{dist}\) array with \(\infty\), and set \(\mathrm{dist}[0] = 0\).
3. Push \((0, 0)\) into a priority queue (min-heap).
4. Pop the vertex \(i\) with the minimum distance from the queue. If the popped distance \(d\) is greater than \(\mathrm{dist}[i]\), it is outdated information, so skip it.
5. For each adjacent cell \(j\) (up, down, left, right) of \(i\), if \(d + A_j < \mathrm{dist}[j]\), update \(\mathrm{dist}[j]\) and push it to the queue.
6. When vertex \(N-1 = HW-1\) (i.e., \((H,W)\)) is popped from the queue, its distance is the answer.

In Dijkstra’s algorithm, the distance to a vertex is finalized the moment it is popped from the queue, so we can immediately output the answer and terminate once the goal is popped (acting as an effective pruning optimization).

The graph has \(N = HW \le 2\times 10^5\) vertices, and since each vertex has at most 4 edges, the number of edges is \(O(HW)\).

Complexity

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

Since \(HW \le 2 \times 10^5\), this is sufficiently fast.

Implementation Details

• Use a 1D array instead of a 2D array: Since either \(H\) or \(W\) can be up to \(10^5\), using the input tokens directly as a 1D array is advantageous in terms of both memory and speed compared to a nested list like A[i][j]. Coordinates can be retrieved from index \(i\) via r, c = divmod(i, W), and movements to the left/right correspond to i-1, i+1, while up/down correspond to i-W, i+W.

• Boundary checks: For left and right moves, be sure to check c > 0 / c+1 < W. Because the grid is flattened into 1D, be careful not to create a bug where moving i+1 when c == W-1 “warps” to the beginning of the next row (vertical moves can be checked simply by testing whether i-W and i+W are within the valid index range).

• Fast I/O: Since there are up to \(HW \le 2\times 10^5\) integers in the input, in Python it is safer to read all input at once using sys.stdin.buffer.read().split().

• Dijkstra with lazy deletion: Discarding outdated entries with if d > dist[i]: continue instead of using a visited array makes the implementation more concise.

• Edge weight is the destination value: The key point is to add nd = d + A[j] (where \(j\) is the destination). If you add A[i] (the current cell), you might mistakenly pay for \(A_{1,1}\) or fail to pay for \(A_{H,W}\), leading to an incorrect answer.

  Source Code

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()

---

This editorial was generated by claude5opus-high.