putnik

#include <bits/stdc++.h>
using namespace std;
const int MN = 2222;
int dp[MN][MN];
int dist[MN][MN];
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin>>n;
    for(int i = 0; i < n; ++i) {
	for(int j = 0; j < n; ++j) {
	    cin>>dist[i][j];
	    dp[i][j] = 1e9;
	}
    }
    dp[0][0] = 0;
    int ans = 1e9;
    for(int i = 0; i < n-1; ++i) {
	for(int j = 0;  j < n-1;++j) {
	    int ma = max(i, j)+1;
	    dp[ma][j] = min(dp[ma][j], dp[i][j]+dist[i][ma]);
	    dp[i][ma] = min(dp[i][ma], dp[i][j]+dist[j][ma]);
	    if(ma == n-1) {
		ans = min(ans, dp[ma][j]);
		ans = min(ans, dp[i][ma]);
	    }
	}
    }
    cout<<ans<<'\n';
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: ACCEPTED

Test 5

Verdict: ACCEPTED

Test 6

Verdict: ACCEPTED

Test 7

Verdict: ACCEPTED

Test 8

Verdict: ACCEPTED