CSES - Leirikisa 4 - Results
Submission details
Task:putnik
Sender:siirikuoppala
Submission time:2016-08-01 16:52:37 +0300
Language:C++
Status:READY
Result:0
Feedback
groupverdictscore
#10
Test results
testverdicttime
#1ACCEPTED0.05 sdetails
#2ACCEPTED0.06 sdetails
#3ACCEPTED0.06 sdetails
#4ACCEPTED0.05 sdetails
#5ACCEPTED0.05 sdetails
#60.07 sdetails
#70.65 sdetails
#80.65 sdetails

Code

#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 details

Test 1

Verdict: ACCEPTED

input
3
0 5 2
5 0 4
2 4 0

correct output
7

user output
7

Test 2

Verdict: ACCEPTED

input
4
0 15 7 8
15 0 16 9
7 16 0 12
8 9 12 0

correct output
31

user output
31

Test 3

Verdict: ACCEPTED

input
5
0 929 320 220 170
929 0 16 856 166
320 16 0 989 554
220 856 989 0 695
...

correct output
1719

user output
1719

Test 4

Verdict: ACCEPTED

input
8
0 506 801 997 312 671 746 780
506 0 634 349 891 378 259 767
801 634 0 806 899 355 545 800
997 349 806 0 780 454 434 962
...

correct output
3214

user output
3214

Test 5

Verdict: ACCEPTED

input
16
0 432 752 452 683 655 785 402 ...

correct output
4696

user output
4696

Test 6

Verdict:

input
300
0 118 579 90 535 606 866 184 1...

correct output
88301

user output
90316

Test 7

Verdict:

input
1500
0 27 341 796 776 497 727 796 5...

correct output
440136

user output
451843

Test 8

Verdict:

input
1499
0 674 891 871 992 186 562 169 ...

correct output
426711

user output
437459