Submission #1799532

---

Source Code Expand

#include <iostream>
#include <tuple>
#include <queue>
#include <algorithm>
#define REP(a, b, c) for (int (a) = (b); (a) < (c); ++a)
using namespace std;
typedef tuple<int, int, int> tiii;
const int INF = 1 << 29;
int N, M;
int A[100][100];
int a, b, c;
queue<tiii> q;
int main(void) {
	cin >> N >> M;
	fill_n(A[0], N * N, INF);
	for (int i = 0; i < M; ++i) {
		cin >> a >> b >> c;
		--a; --b;
		A[a][b] = A[b][a] = c;
		q.push(tiii(a, b, c));
	}
	REP(k, 0, N) REP(i, 0, N) REP(j, 0, N) {
		A[i][j] = min(A[i][j], A[i][k] + A[k][j]);
	}
	int ans = M;
	while (!q.empty()) {
		tie(a, b, c) = q.front(); q.pop();
		if (A[a][b] == c) --ans;
	}
	cout << ans << endl;
	return 0;
}

Submission Info

Judge Result