Submission #1598573


Source Code Expand

Copy
#include <iostream>
#include <vector>
#include <algorithm>

#define REP(i,a,b) for(int i=int(a);i<int(b);i++)

using namespace std;

typedef long long int lli;

int main () {
    int N;
    cin >> N;
    vector<vector<int>> A(N, vector<int>(N));
    lli ans = 0;
    for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) {
        cin >> A[i][j];
        ans += A[i][j];
    }

    bool check = true;
    for (int s = 0; s < N; s++) {
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (A[i][j] > A[i][s] + A[s][j]) {
                    check = false;
                }
            }
        }
    }
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            bool isSame = false;
            for (int s = 0; s < N; s++) {
                if (i == s || s == j) continue;
                if (A[i][j] == A[i][s] + A[s][j]) {
                    isSame = true;
                }
            }
            if (isSame) {
                ans -= A[i][j];
            }
        }
    }
    if (!check) {
        cout << -1 << endl;
    } else {
        cout << ans / 2 << endl;
    }
    return 0;
}

Submission Info

Submission Time
Task D - Restoring Road Network
User commy
Language C++14 (GCC 5.4.1)
Score 500
Code Size 1218 Byte
Status
Exec Time 108 ms
Memory 640 KB

Test Cases

Set Name Score / Max Score Test Cases
Sample 0 / 0 subtask0_0.txt, subtask0_1.txt, subtask0_2.txt, subtask0_3.txt
All 500 / 500 01.txt, 02.txt, 03.txt, 04.txt, 05.txt, 06.txt, 07.txt, 08.txt, 09.txt, 10.txt, 11.txt, 12.txt, 13.txt, subtask0_0.txt, subtask0_1.txt, subtask0_2.txt, subtask0_3.txt
Case Name Status Exec Time Memory
01.txt 108 ms 640 KB
02.txt 108 ms 640 KB
03.txt 107 ms 640 KB
04.txt 108 ms 640 KB
05.txt 108 ms 640 KB
06.txt 107 ms 640 KB
07.txt 103 ms 640 KB
08.txt 99 ms 640 KB
09.txt 99 ms 640 KB
10.txt 103 ms 640 KB
11.txt 104 ms 640 KB
12.txt 108 ms 640 KB
13.txt 1 ms 256 KB
subtask0_0.txt 1 ms 256 KB
subtask0_1.txt 1 ms 256 KB
subtask0_2.txt 1 ms 256 KB
subtask0_3.txt 1 ms 256 KB