Submission #1127102

---

Source Code Expand

#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;
const int MAX_N = 100;
const int MAX_M = 1000;
const int INF = 1e8;

int cnt, N, M;
bool used[MAX_N];
int dist[MAX_N][MAX_N];
int cost[MAX_N][MAX_N] {};

void dijkstra(int s) {
  fill(used, used + N, false);
  dist[s][s] = 0;
  while (1) {
    int u = -1;
    rep(v, N) {
      if (!used[v] && (u == -1 || dist[s][v] < dist[s][u])) u = v;
    }
    if (u == -1) break;
    used[u] = true;
    rep(v, N) {
      dist[s][v] = min(dist[s][v], dist[s][u] + cost[u][v]);
    }
  }
}

main() {
  cin >> N >> M;
  rep(i, M) {
    int a, b, c;
    cin >> a >> b >> c;
    a--; b--;
    cost[a][b] = cost[b][a] = c;
  }
  fill((int*)dist, (int*)(dist + N), INF);
  rep(s, N) dijkstra(s);
  cnt = 0;
  rep(i, N) {
    rep(j, N) {
      if (i >= j || cost[i][j] == 0) continue;
      bool shortest = false;
      rep(s, N) {
        if (dist[s][j] == dist[s][i] + cost[i][j]) {
          shortest = true;
          continue;
        }
      }
      if (shortest) cnt++;
    }
  }
  cout << M - cnt << endl;
}

Submission Info

Judge Result