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
Exec Time 100 ms
Memory 1664 KB

Judge Result

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 85 ms 1664 KB
02.txt 85 ms 1664 KB
03.txt 85 ms 1664 KB
04.txt 87 ms 1664 KB
05.txt 89 ms 1664 KB
06.txt 100 ms 1664 KB
07.txt 79 ms 1664 KB
08.txt 80 ms 1664 KB
09.txt 81 ms 1664 KB
10.txt 79 ms 1664 KB
11.txt 79 ms 1664 KB
12.txt 84 ms 1664 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