putnik

#include <iostream>

using namespace std;

int t[1555][1555], h[1555][1555], a[1555][1555];
int main(){
    int n;
    cin >> n;
    for(int i=1; i<=n; ++i){
        for(int j=1; j<=n; ++j){
            cin >> t[i][j];
            h[i][j]=1e9;
        }
    }
    for(int i=1; i<=n; ++i) h[1][i]=0;
    a[1][1]=1;
    for(int i=2; i<=n; ++i){
        for(int j=1; j<i; ++j){
            if(h[i-1][j]+t[j][i] < h[i][i]){
                a[i][i]=a[i-1][j];
                h[i][i]=h[i-1][j]+t[j][i];
            }
            h[i][j]=h[i-1][j]+t[i][a[i-1][j]];
            a[i][j]=i;
        }
    }
    int v=1e9;
    for(int i=1; i<=n; ++i){
        v=min(v, h[n][i]);
    }
    cout << v;
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: ACCEPTED

Test 5

Verdict: ACCEPTED

Test 6

Verdict: WRONG ANSWER

Test 7

Verdict: WRONG ANSWER

Test 8

Verdict: WRONG ANSWER