fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std; 
  3.  
  4. #define FAST_IO ios_base::sync_with_stdio(0);cin.tie(0);
  5. #define endl '\n'
  6. #define pb push_back
  7. #define eb emplace_back
  8. #define ff first
  9. #define ss second
  10. #define all(x) (x).begin(), (x).end()
  11. #define rall(x) (x).rbegin(), (x).rend()
  12.  
  13. #define dbg(x) cout << #x << " = " << x << endl
  14.  
  15. typedef long long ll;
  16. typedef pair<int, int> pi;
  17.  
  18. const ll MOD = 1e9 + 7;
  19. const int INF = 0x3f3f3f3f;
  20. const ll LINF = 0x3f3f3f3f3f3f3f3fll;
  21.  
  22. #define MAXN 105
  23.  
  24. // n -> número de vértices
  25. int n;
  26. int w[MAXN][MAXN];
  27. int dist[MAXN][MAXN];
  28.  
  29. void floyd_warshall() {
  30.     for (int k = 0 ; k < n ; k++) {
  31.         for (int i = 0 ; i < n ; i++) {
  32.             for (int j = 0 ; j < n ; j++) {
  33.                 dist[i][j] = min(dist[i][j] , dist[i][k] + dist[k][j]) ;
  34.             }
  35.         }
  36.     }
  37. }
  38. void initialize() {
  39.     for (int i = 0 ; i < n ; i++) {
  40.         for (int j = 0 ; j < n ; j++) {
  41.             if (i == j) {
  42.                 dist[i][j] = 0;
  43.             } else {
  44.                 dist[i][j] = INF ;
  45.             }
  46.         }
  47.     }
  48. }
  49.  
  50. signed main(){
  51.     FAST_IO
  52.  
  53.     cin >> n;
  54.  
  55.     initialize();
  56.  
  57.     for (int i = 0 ; i < n; i++) {
  58.         for (int j = 0; j < n; j++) {
  59.             int c; cin >> c;
  60.             w[i][j] = c;
  61.             dist[i][j] = min(dist[i][j], c);
  62.         }
  63.     }
  64.  
  65.     floyd_warshall();
  66.  
  67.     // Passo 1: Verificar a coerência da Matriz
  68.     // -> Verifique se w[i][j] (voo direto) > dist[i][j]
  69.     for (int i = 0; i < n; i++) {
  70.         for (int j = 0; j < n; j++) {
  71.             if (i != j && dist[i][j] < w[i][j]) {
  72.                 cout << -1 << endl;
  73.                 return 0;
  74.             }
  75.         }
  76.     }
  77.  
  78.     // Passo 2: Contar voos diretos que podemos remover
  79.     // -> Verificar se existe um k, com k != i e k != j, t.q. w[i][j] == w[i][k] + w[k][j]
  80.     int ans = 0;
  81.     for (int i = 0; i < n; i++) {
  82.         for (int j = i+1; j < n; j++) {
  83.             for (int k = 0; k < n; k++) {
  84.                 if (k == i || k == j) continue;
  85.                 if (w[i][j] == w[i][k] + w[k][j]) {
  86.                     // Encontramos um caminho i -> k -> j alternativo para i -> j
  87.                     ans++;
  88.                     break; // Não precisamos testar os outros k
  89.                 }
  90.             }
  91.         }
  92.     } 
  93.  
  94.     cout << ans << endl;
  95. }
Success #stdin #stdout 0s 5308KB
comments (?)
stdin 
Standard input is empty
stdout 
0
https://ideone.com/1XyEkD
language:
C++14 (gcc 8.3)
created:
1 day ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!