Submission #1608705

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;

#define INF 900000000
#define LINF 9000000000000000000

typedef long long ll;
typedef pair<int, int> P;

int n, m;
int d[101][101];
int a[1000], b[1000], c[1000];

int main(){
	cin.tie(0);
  ios::sync_with_stdio(false);

	for (int i = 0; i < 101; i++) for (int j = 0; j < 101; j++) d[i][j] = (i==j?0:INF);

	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		cin >> a[i] >> b[i] >> c[i]; a[i]--, b[i]--;
	}

	for (int i = 0; i < m; i++) {
		d[a[i]][b[i]] = min(d[a[i]][b[i]], c[i]);
		d[b[i]][a[i]] = min(d[b[i]][a[i]], c[i]);
	}

	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]);
			}
		}
	}

	int ans = m;
	for (int i = 0; i < m; i++) {
		bool srt = false;
		for (int j = 0; j < n; j++) if (d[j][a[i]]+c[i] == d[b[i]][j]) srt = true;
		if (srt) ans--;
	}

	cout << ans << endl;

	return 0;
}

Submission Info

Judge Result