Submission #19408234

---

Source Code Expand

#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

Judge Result