Зимняя школа в "Эврике"

Теперь решим задачу о нахождении маршрута минимальной стоимости из левого верхнего угла в правый нижний, считая что для каждой клетке 
указана стоимость прохода через эту клетку. 
Сразу же будем считать, что таблица снабжена «каемочкой», поэтому начальная клетка будет иметь индексы (1, 1), конечная клетка — (n, m), 
а строка и столбец с индексом 0 будут относится к фиктивной каемочке.

Если считать, что стоимость прохода через клетку (i, j) записана в отдельном списке Price[i, j], то обозначив через С(i, j) стоимость 
кратчайшего пути из начальной клетки (1, 1) в клетку (i, j) получим рекуррентное соотношение: 
C(i, j) = min(C(i, j − 1), C(i − 1, j), C(i − 1, j − 1)) + Price[i, j]
При этом при вычислении граничных значений (в первом столбце и первой строке) необходимо учитывать только клетки из этого столбца и этой
строки (но не из предыдущего столбца и предыдущей строки). 
Это удобно реализовать, если заполнить предыдущую строк и предыдущий столбец «каемочкой», записав для клеток каемочки значения функции C 
равными некоторому очень большому числу. 
Это число мы будем обозначать как INF, в качестве значения INF следует взять число, заведомо больше, чем максимальное число, 
которое может быть записано в таблице C. А в угол «каемочки» нужно записать число 0: C[0][0] = 0.

INF = 10 ** 20
C = [[0] * (m + 1) for i in range(n + 1)]
C[0][0] = 0
for i in range(1, n + 1):
    C[i][0] = INF
for j in range(1, m + 1):
    C[0][j] = INF
for i in range(1, n + 1):
    for j in range(1, m + 1):
        C[i][j] = min(C[i][j - 1], C[i - 1][j], C[i - 1][j - 1]) + Price[i][j]