putnik

#include <iostream>
using namespace std;
int N;

int dp[1515][1515];

int rt[1515][1515];

int main(){
  cin >> N;
  for (int i=0; i<N; ++i){
    for (int j=0; j<N; ++j){
      cin >> rt[i][j];
    }
  }
  dp[1][0]=rt[1][0];
  for (int i=2; i<N; ++i){
    dp[i][i-1]=1222333444;
    for (int j=0; j<i-1; ++j){
      dp[i][j]=dp[i-1][j]+rt[i][i-1];
      dp[i][i-1]=min(dp[i][i-1], dp[i-1][j]+rt[i][j]);
    }
  }
  int ans=1222333444;
  for (int i=0; i<N-1; ++i) ans=min(ans, dp[N-1][i]);
  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