Submission #3775875

---

Source Code Expand

#include <iostream>
using namespace std;

int main () {
  int n, m;  
  cin >> n >> m;
  int a[m], b[m], c[m];
  int edge[n + 1][n + 1];
  int stand[n + 1][n + 1];
  for (int i = 0; i <= n; i++) {
    for (int j = 0; j <= n; j++) {
      edge[i][j] = 1001;
    }  
  }
  for (int i = 0; i < m; i++) {
    cin >> a[i] >> b[i] >> c[i];
    edge[a[i]][b[i]] = c[i]; 
    edge[b[i]][a[i]] = c[i]; 
  }
  int original[n + 1][n + 1];
  for (int i = 0; i <= n; i++) {
    for (int j = 0; j <= n; j++) {
      if (edge[i][j] != 1001) {
        original[i][j] = edge[i][j]; 
      }
      else {
        original[i][j] = 0;  
      }
    }  
  }
  for (int k = 1; k <= n; k++) {
    for (int i = 1; i <= n; i++) {
      for (int j = 1; j <= n; j++) {
        if (edge[i][j] > edge[i][k] + edge[k][j]) {
          edge[i][j] = edge[i][k] + edge[k][j];  
        }    
      }  
    }    
  }
  int ans = 0;
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++) {
      if (original[i][j] != 0 && original[i][j] != edge[i][j]) {
        ans++;  
      }
    }  
  }
  cout << ans / 2 << endl;

}

Submission Info

Judge Result