Submission #19408234


Source Code Expand

Copy
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
int main () {
  int N;
  cin >> N;
  vector<tuple<ll, int, int>> road;
  int A[303][303];
  for (int i = 0; i < N; i ++) {
    for (int j = 0; j < N; j ++) {
      cin >> A[i][j];
      if (i < j) {
        road.push_back(make_tuple(A[i][j], i, j));
      }
    }
  }
  sort(road.begin(), road.end());
  ll ans[303][303];
  ll INF = 1e16;
  for (int i = 0; i < N; i ++) {
    for (int j = 0; j < N; j ++) {
      ans[i][j] = INF;
      if(i == j) ans[i][j] = 0;
    }
  }
  ll ret = 0;
  for (int i = 0; i < (int)road.size(); i ++) {
    ll L;
    int a, b;
    tie(L, a, b) = road[i];
    if (ans[a][b] < L) {
      cout << -1 << endl;
      return 0;
    }
    if (ans[a][b] > L) {
      ret += L;
      ans[a][b] = ans[b][a] = L;
      for (int p = 0; p < N; p ++) {
        for (int q = 0; q < N; q ++) {
          ans[p][q] = 
            min(ans[p][q], 
                min(ans[p][a] + L + ans[b][q], ans[p][b] + L + ans[a][q]));
          ans[q][p] = ans[p][q];
        }
      }
    }
  }
  cout << ret << endl;
}

Submission Info

Submission Time
Task D - Restoring Road Network
User kumjin3141
Language C++ (GCC 9.2.1)
Score 500
Code Size 1136 Byte
Status AC
Exec Time 163 ms
Memory 5276 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 500 / 500
Status
AC × 4
AC × 17
Set Name Test Cases
Sample subtask0_0.txt, subtask0_1.txt, subtask0_2.txt, subtask0_3.txt
All 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 AC 84 ms 5176 KB
02.txt AC 81 ms 5164 KB
03.txt AC 82 ms 5072 KB
04.txt AC 82 ms 5172 KB
05.txt AC 82 ms 5104 KB
06.txt AC 88 ms 5276 KB
07.txt AC 92 ms 5132 KB
08.txt AC 156 ms 5036 KB
09.txt AC 163 ms 5104 KB
10.txt AC 94 ms 5188 KB
11.txt AC 100 ms 5112 KB
12.txt AC 76 ms 5192 KB
13.txt AC 2 ms 3448 KB
subtask0_0.txt AC 2 ms 3612 KB
subtask0_1.txt AC 2 ms 3512 KB
subtask0_2.txt AC 2 ms 3520 KB
subtask0_3.txt AC 2 ms 3584 KB