1. Идея

Нужно найти путь по сетке из клетки (1, 1) в клетку (n, m) с минимальной суммой тарифов.

Если смотреть на задачу как на граф:

• каждая клетка — это вершина;
• из клетки можно перейти в 4 соседние клетки;
• стоимость перехода в соседнюю клетку равна тарифу этой соседней клетки.

Все веса неотрицательны, значит для поиска кратчайшего пути подходит алгоритм Дейкстры.

Важно: тариф стартовой клетки не учитывается, поэтому начальное расстояние до клетки (1, 1) равно 0.

2. Наблюдения

1. Переходы имеют разные стоимости, поэтому обычный BFS не подходит.
2. Все стоимости неотрицательные, значит алгоритм Дейкстры работает корректно.
3. Удобно хранить dist[x][y] — минимальную стоимость добраться до клетки с координатами (x, y).
4. Если мы находимся в клетке (x, y) с текущей стоимостью d, то для соседней клетки (nx, ny) новая стоимость будет:
   • nd = d + a[nx][ny]
5. Начальная клетка особенная:
   • dist[0][0] = 0
   • в ответ тариф a[0][0] не входит.
6. Так как одна и та же клетка может несколько раз попадать в очередь с разными значениями, нужно пропускать устаревшие записи:
   • если извлечённое d не равно dist[x][y], значит это старое значение.

3. Алгоритм

1. Считываем n, m и таблицу тарифов a.
2. Создаём массив dist размера n x m, заполняем его очень большим числом.
3. Присваиваем dist[0][0] = 0.
4. Создаём приоритетную очередь, в которую кладём состояние (0, 0, 0):
   • текущая стоимость 0,
   • координаты x = 0, y = 0.
5. Пока очередь не пуста:
   • извлекаем клетку с минимальной стоимостью;
   • если это устаревшая запись, пропускаем её;
   • если это клетка (n - 1, m - 1), можно завершить работу;
   • перебираем 4 соседей;
   • если сосед находится внутри сетки, пробуем улучшить его расстояние:
     • nd = d + a[nx][ny]
     • если nd < dist[nx][ny], обновляем dist[nx][ny] и добавляем новое состояние в очередь.
6. Выводим dist[n - 1][m - 1].

4. Почему это работает

Алгоритм Дейкстры находит кратчайшие пути от стартовой вершины до всех остальных в графе с неотрицательными весами.

В этой задаче:

• вершины графа — клетки сетки;
• рёбра существуют между соседними по стороне клетками;
• вес ребра равен стоимости клетки, в которую мы переходим;
• все веса неотрицательны.

Значит условия применимости алгоритма выполнены.

Почему значение dist[x][y] действительно означает минимальную стоимость попасть в клетку (x, y):

• сначала известно только dist[0][0] = 0;
• далее мы всегда извлекаем из приоритетной очереди клетку с наименьшей текущей стоимостью;
• если извлечённое значение совпадает с dist[x][y], то это уже наименьшая возможная стоимость добраться до этой клетки;
• после этого мы пытаемся улучшить соседние клетки через неё.

Так как все переходы имеют неотрицательную стоимость, более выгодный путь в уже подтверждённую клетку позже появиться не может. Это и есть ключевое свойство Дейкстры.

Отдельно про стартовую клетку:

• робот уже находится в (1, 1), поэтому платить за неё не нужно;
• именно поэтому начальное расстояние равно 0, а не a[0][0].

Следовательно, после завершения алгоритма dist[n - 1][m - 1] — минимальная суммарная стоимость пути до финиша.

5. Сложность

Пусть всего клеток V = n * m.

У каждой клетки не более 4 соседей, значит число переходов E пропорционально V.

Тогда сложность алгоритма Дейкстры:

• по времени: O(n * m * log(n * m))
• по памяти: O(n * m)

Это укладывается в ограничения задачи.

6. Код на C++17

#include <iostream>
#include <vector>
#include <queue>
#include <tuple>
#include <limits>

using namespace std;

int main() {
    int n, m;
    cin >> n >> m;

    vector<vector<int>> a(n, vector<int>(m));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> a[i][j];
        }
    }

    const long long INF = numeric_limits<long long>::max();
    vector<vector<long long>> dist(n, vector<long long>(m, INF));

    priority_queue<
        tuple<long long, int, int>,
        vector<tuple<long long, int, int>>,
        greater<tuple<long long, int, int>>
    > pq;

    dist[0][0] = 0;
    pq.push({0, 0, 0});

    int dx[4] = {-1, 1, 0, 0};
    int dy[4] = {0, 0, -1, 1};

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

        if (d != dist[x][y]) {
            continue;
        }

        if (x == n - 1 && y == m - 1) {
            break;
        }

        for (int k = 0; k < 4; k++) {
            int nx = x + dx[k];
            int ny = y + dy[k];

            if (nx < 0 || nx >= n || ny < 0 || ny >= m) {
                continue;
            }

            long long nd = d + a[nx][ny];
            if (nd < dist[nx][ny]) {
                dist[nx][ny] = nd;
                pq.push({nd, nx, ny});
            }
        }
    }

    cout << dist[n - 1][m - 1] << "\n";
    return 0;
}

7. Код на Python 3

import heapq

n, m = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(n)]

inf = 10**30
dist = [[inf] * m for _ in range(n)]
dist[0][0] = 0

pq = [(0, 0, 0)]

dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

while pq:
    d, x, y = heapq.heappop(pq)

    if d != dist[x][y]:
        continue

    if x == n - 1 and y == m - 1:
        break

    for k in range(4):
        nx = x + dx[k]
        ny = y + dy[k]

        if 0 <= nx < n and 0 <= ny < m:
            nd = d + a[nx][ny]
            if nd < dist[nx][ny]:
                dist[nx][ny] = nd
                heapq.heappush(pq, (nd, nx, ny))

print(dist[n - 1][m - 1])