Submission #1070311

---

Source Code Expand

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#define INF (1<<30)
using namespace std;
struct Edge {
	int a, b, cost;
	Edge() {}
	Edge(int a, int b, int cost) :a(a), b(b), cost(cost) {}
	bool operator < (Edge& o) const{
		return cost < o.cost;
	}
};
int main() {
	cin.tie(0); ios::sync_with_stdio(false);
	int N, M; cin >> N >> M;
	vector<vector<Edge>> G(N + 1);
	vector<Edge> e(N + 1);
	vector<vector<int>> dist(N + 1, vector<int>(N + 1, INF));

	//	initialize
	for (int i = 0; i < M;i++) {
		int a, b, c; cin >> a >> b >> c;
		G[a].emplace_back(Edge(a, b, c));
		G[b].emplace_back(Edge(b, a, c));

		e[i] = Edge(a, b, c);
	}
	// dist[i][j] = i-j間の最短距離
	for (int i = 1; i <= N; i++) {
		queue<int> q;
		dist[i][i] = 0;
		q.push(i);

		while (!q.empty()) {
			int n = q.front(); q.pop();
			for (auto o : G[n]) {
				int next = o.b;
				if (dist[i][n] + o.cost < dist[i][next]) {
					dist[i][next] = dist[i][n] + o.cost;
					q.push(next);
				}
			}
		}
	}
	
	int ans = M;
	for (int i = 0; i < M; i++) {
		bool f = false;
		for (int j = 1; j <= N; j++) { if (dist[j][e[i].a] + e[i].cost == dist[j][e[i].b]) f = true; }
		if (f) ans--;
	}

	cout << ans << endl;
	
}

Submission Info

Judge Result