Submission #19408229


Source Code Expand

Copy
#include<bits/stdc++.h>
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 0
Code Size 1114 Byte
Status CE

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:5:3: error: ‘cin’ was not declared in this scope; did you mean ‘std::cin’?
    5 |   cin >> N;
      |   ^~~
      |   std::cin
In file included from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:75,
                 from ./Main.cpp:1:
/usr/include/c++/9/iostream:60:18: note: ‘std::cin’ declared here
   60 |   extern istream cin;  /// Linked to standard input
      |                  ^~~
./Main.cpp:6:3: error: ‘vector’ was not declared in this scope
    6 |   vector<tuple<ll, int, int>> road;
      |   ^~~~~~
./Main.cpp:6:3: note: suggested alternatives:
In file included from /usr/include/c++/9/vector:67,
                 from /usr/include/c++/9/functional:62,
                 from /usr/include/c++/9/pstl/glue_algorithm_defs.h:13,
                 from /usr/include/c++/9/algorithm:71,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:65,
                 from ./Main.cpp:1:
/usr/include/c++/9/bits/stl_vector.h:386:11: note:   ‘std::vector’
  386 |     class vector : protected _Vector_base<_Tp, _Alloc>
      |           ^~~~~~
In file included from /usr/include/c++/9/functional:62,
                 from /usr/include/c++/9/pstl/glue_algorithm_defs.h:13,
                 from /usr/include/c++/9/algorithm:71,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:65,
                 from ./Main.cpp:1:
/usr/include/c++/9/vector:90:13: note:   ‘std::pmr::vector’
   90 |       using vector = std::vector<_Tp, polymorphic_allocator<_Tp>>;
      |             ^~~~~~
./Main.cpp:6:10: error: ‘tuple’ was not declared in this scope; did you mean ‘std::tuple’?
    6 |   vector<tuple<ll, int, int>> road;
      |          ^~~~~
      |          std::tuple
In file included from /usr/include/c++/9/bits/move.h:55,
                 from /usr/include/c++/9/bits/stl_pair.h:59,
                 from /usr/include/c++/9/bits/stl_algobase.h:64,
                 from /usr/include/c++/9/bits/specfun.h:45,
          ...