Overview

This problem asks for the minimum total toll paid when moving from the top-left cell \((1, 1)\) to the bottom-right cell \((H, W)\) on an \(H \times W\) grid, given the rule that you must pay a cell’s toll whenever you enter it.

Analysis

Reduction to a Graph Problem

This problem can be viewed as a shortest path problem by treating each cell as a “vertex” and the transitions between adjacent cells in the four cardinal directions (up, down, left, right) as “directed edges”.

Since a toll \(A_{r, c}\) is incurred every time you move into cell \((r, c)\), we set the weight of all directed edges entering cell \((r, c)\) to \(A_{r, c}\). Because you do not pay the toll for the starting cell \((1, 1)\) initially, the cost at the initial state (travel distance \(0\)) is \(0\).

Why Simple Dynamic Programming (DP) Does Not Work

When seeing “moving from the top-left to the bottom-right”, one might typically think of dynamic programming (DP). However, in this problem, movement in all \(4\) directions (up, down, left, right) is allowed. For instance, if the toll of the cell directly to the right is extremely large, it might end up being cheaper to detour up or down first. Because paths can contain loops or backtracking, this cannot be solved with a simple DP that restricts the visitation order of cells to a single direction.

Applying Dijkstra’s Algorithm

Since all tolls \(A_{i, j}\) are non-negative, the edge weights are non-negative. A single-source shortest path problem without negative edge weights can be solved efficiently using Dijkstra’s algorithm.

Algorithm

We apply Dijkstra’s algorithm using a priority queue (heap).

1. 1D Flattening of Vertices: Represent the \(H \times W\) cells \((i, j)\) (\(0\)-indexed) with a single integer index \(u = i \times W + j\).
2. Initialization:
   • Prepare an array dist to store the minimum cost from the start to each cell, and initialize all values to a sufficiently large value (\(\infty\)).
   • Set the cost of the starting vertex \(u = 0\) (cell \((0, 0)\)) to \(0\), and push (cost 0, vertex 0) to the priority queue.
3. Search:
   • Pop the vertex \(u\) with the minimum tentative cost from the priority queue.
   • If the popped cost is greater than the currently recorded dist[u], ignore it.
   • If \(u\) is the destination vertex (\(H \times W - 1\)), the shortest path to it has been determined; terminate the search and output the cost.
   • For each cell \(v\) adjacent to \(u\) in the four directions, if the new cost \(d + A_v\) (adding the entry toll \(A_v\) for vertex \(v\)) is less than dist[v], update dist[v] and push it into the priority queue.

Complexity

• Time Complexity: \(O(HW \log(HW))\)
  • The number of vertices is \(V = H \times W\), and since each vertex has at most \(4\) outgoing edges, the number of edges is \(E \le 4HW\).
  • The time complexity of Dijkstra’s algorithm is \(O(E \log V)\), which yields \(O(HW \log(HW))\) overall.
  • Given the constraint \(HW \le 2 \times 10^5\), the number of operations is approximately \(3.6 \times 10^6\), which easily runs well within the time limit.
• Space Complexity: \(O(HW)\)
  • Memory of \(O(HW)\) is used for the array storing tolls, the shortest distance array dist, and the priority queue.

Implementation Details

• Grid Flattening and Boundary Checks: Letting \(u\) be the cell index, you can check whether moving left or right is valid by examining \(u \pmod W\):

  • Upward movement: possible when \(u \ge W\) (destination: \(u - W\))
  • Downward movement: possible when \(u < HW - W\) (destination: \(u + W\))
  • Leftward movement: possible when \(u \pmod W \neq 0\) (destination: \(u - 1\))
  • Rightward movement: possible when \(u \pmod W \neq W - 1\) (destination: \(u + 1\))

• Fast I/O: Since the input size is large (up to \(2 \times 10^5\) or more integers), reading the entire input at once using sys.stdin.read().split() in Python significantly reduces the runtime spent on I/O.

• Early Termination upon Reaching the Destination: In Dijkstra’s algorithm, the shortest path to a vertex is finalized the moment it is popped from the heap. Stopping the process and printing the result as soon as the destination vertex is popped avoids redundant computations.

  Source Code

import sys
import heapq

def solve():
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    H = int(input_data[0])
    W = int(input_data[1])
    
    A = [int(x) for x in input_data[2:]]
    
    total_nodes = H * W
    INF = 10**18
    dist = [INF] * total_nodes
    dist[0] = 0
    
    pq = [(0, 0)]
    target = total_nodes - 1
    
    while pq:
        d, u = heapq.heappop(pq)
        
        if d > dist[u]:
            continue
        
        if u == target:
            print(d)
            return
            
        mod = u % W
        
        # 上
        if u >= W:
            v = u - W
            nd = d + A[v]
            if nd < dist[v]:
                dist[v] = nd
                heapq.heappush(pq, (nd, v))
        # 下
        if u < total_nodes - W:
            v = u + W
            nd = d + A[v]
            if nd < dist[v]:
                dist[v] = nd
                heapq.heappush(pq, (nd, v))
        # 左
        if mod != 0:
            v = u - 1
            nd = d + A[v]
            if nd < dist[v]:
                dist[v] = nd
                heapq.heappush(pq, (nd, v))
        # 右
        if mod != W - 1:
            v = u + 1
            nd = d + A[v]
            if nd < dist[v]:
                dist[v] = nd
                heapq.heappush(pq, (nd, v))

if __name__ == '__main__':
    solve()

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