GRD3-T17: Min Cost Path 2

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

typedef pair<int, int> pii;

const int mov[3] = {-1, 0, 1};
const int NR = 10;
const int NC = 100;

int board[NR + 1][NC + 1], dp[NR + 1][NC + 1], par[NR + 1][NC + 1];
int row, col;

int main(){

    scanf("%d %d", &row, &col);
    for(int i = 1; i <= row; ++i){
        for(int j = 1; j <= col; ++j){
            scanf("%d", &board[i][j]);
        }
    }

    for(int j = col; j >= 1; --j){
        for(int i = 1; i <= row; ++i){
            int mn = 1e9;
            for(int m = 0; m < 3; ++m){
                int nr = i + mov[m];
                if(nr == 0){
                    nr = row;
                } else if(nr == row + 1){
                    nr = 1;
                }
                if(dp[nr][j + 1] < mn || (dp[nr][j + 1] == mn && nr < par[i][j])){
                    mn = dp[nr][j + 1];
                    par[i][j] = nr;
                }
            }
            dp[i][j] = mn + board[i][j];
        }
    }

    int mn = 1e9;
    int bestRow = 0;
    for(int i = 1; i <= row; ++i){
        if(dp[i][1] < mn){
            mn = dp[i][1];
            bestRow = i;
        }
    }

    int i = bestRow;
    for(int j = 1; j <= col; ++j){
        cout << i << " ";
        i = par[i][j];
    }
    cout << "\n" << mn;

    return 0;
}