Submission #4190487


Source Code Expand

Copy
#include <bits/stdc++.h>
#define int long long int
#define mod(x) ((x % MOD) + MOD) % MOD
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define FORE(i,a,b) for(int i=(a);i<=(b);++i)
#define RFOR(i,a,b) for(int i=(b)-1;i>=(a);--i)
#define RFORE(i,a,b) for(int i=(b);i>=(a);--i)
#define REP(i,n) FOR(i,0,n)
#define ALL(c) (c).begin(),(c).end()
#define RALL(c) (c).rbegin(),(c).rend()
#define SORT(c) sort(ALL(c))
#define RSORT(c) sort(RALL(c))
#define SZ(c) (int)((c).size())
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define LB(c,x) (int)(lower_bound(ALL(c),x)-(c).begin())
#define UB(c,x) (int)(upper_bound(ALL(c),x)-(c).begin())
#define COUNT(c,x) (UB(c,x)-LB(c,x))
#define UNIQUE(c) SORT(c); (c).erase(unique(ALL(c)),(c).end());
#define COPY(c1,c2) copy(ALL(c1),(c2).begin())
#define EXIST(s,e) (bool)((s).find(e)!=(s).end())
#define PB push_back
#define MP make_pair
#define DEL(v) decltype(v)().swap(v)
#define DUMP(x)  cerr << #x << " = " << (x) << endl;
using namespace std;
template<typename T1, typename T2> using P = pair<T1,T2>;
template<typename T> using V = vector<T>;
struct edge { int from, to; int cost; };
bool operator< (const edge &edge1, const edge &edge2) { return edge1.cost < edge2.cost; };
const int INF = 1e18;
const int MOD = 1e9+7;

template<typename T> ostream& operator << (ostream& s, const V<T>& v) {
   s << "[";
   for (int i = 0; i < v.size(); i++) { s << v[i]; if (i < v.size() - 1) s << " "; }
   s << "]";
   return s;
}

void bellman(const V<V<int>>& A, V<int>& d)
{
   int N = SZ(A);
   REP(k, N) REP(i, N) REP(j, N) d[i] = min(d[i], d[j] + A[i][j]);
}

void warshall_floyd(vector< vector<int> >& d)
{
   int N = d.size();
   for (int k = 0; k < N; k++) {
      for (int i = 0; i < N; i++) {
         for (int j = 0; j < N; j++) {
            d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
         }
      }
   }
}


template<typename T1, typename T2> ostream& operator << (ostream& s, const P<T1,T2>& p) {
   s << "(" << p.first << "," << p.second << ")";
   return s;
}

signed main()
{
   int N; cin >> N;
   V<V<int>> A(N,V<int>(N));
   REP(i,N) REP(j,N) cin >> A[i][j];

   V<V<int>> d(N,V<int>(N));
   REP(i, N) COPY(A, d);
   warshall_floyd(d);

   bool flag = true;
   FOR(i, 0, N) FOR(j, i+1, N) if (d[i][j] < A[i][j]) flag = false;
   if (!flag) {
      cout << -1 << endl; return 0;
   }

   int ans = 0;
   FOR(i, 0, N) {
      FOR(j, i+1, N) {
         bool canRemove = false;
         REP(k, N) {
            if (i == k || j == k) continue;
            if (d[i][j] == d[i][k] + d[k][j]) {
               canRemove = true;
               break;
            }
         }
         if (!canRemove) ans += A[i][j];
      }
   }
   cout << ans << endl;

   return 0;
}

Submission Info

Submission Time
Task D - Restoring Road Network
User habara_k
Language C++14 (GCC 5.4.1)
Score 500
Code Size 2841 Byte
Status AC
Exec Time 100 ms
Memory 1664 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 85 ms 1664 KB
02.txt AC 85 ms 1664 KB
03.txt AC 85 ms 1664 KB
04.txt AC 87 ms 1664 KB
05.txt AC 89 ms 1664 KB
06.txt AC 100 ms 1664 KB
07.txt AC 79 ms 1664 KB
08.txt AC 80 ms 1664 KB
09.txt AC 81 ms 1664 KB
10.txt AC 79 ms 1664 KB
11.txt AC 79 ms 1664 KB
12.txt AC 84 ms 1664 KB
13.txt AC 1 ms 256 KB
subtask0_0.txt AC 1 ms 256 KB
subtask0_1.txt AC 1 ms 256 KB
subtask0_2.txt AC 1 ms 256 KB
subtask0_3.txt AC 1 ms 256 KB