Submission #2716680

---

Source Code Expand

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <cmath>

using namespace std;

#define REP(i,n) for (int i=0;i<(n);++i)
#define REP2(i,n) for (int i=0;i<=(n);++i)
#define REP3(i,n) for (int i=1;i<=(n);++i)

static const int MAXN = 1001;
static const int MAXM = 1001;
static const int INF = 1e5;

int N, M;
int G[MAXN][MAXN];

int a[MAXM],b[MAXM];

int dist[MAXN][MAXN];

int main() {

	REP(i, MAXN) {
		REP(j, MAXN) {
			G[i][j] = INF;
		}
	}

	cin >> N >> M;
	REP(i, M) {
		int ai,bi,ci;
		cin >> ai >> bi >> ci;
		G[ai][bi] = ci;
		G[bi][ai] = ci;
		a[i] = ai;
		b[i] = bi;
	}

	//Dijkstra's Algorithm
	REP3(i, N) {
		int color[MAXN];//white=1,gre=2,black=3
		int p[MAXN];
		REP3(j, N) {
			dist[i][j] = INF;
			color[j] = 1;
		}
		dist[i][i] = 0;
		p[i] = -1;

		while (true) {
			int mincost,u;
			mincost = INF;
			REP3(j, N) {
				if ((color[j] != 3) && (dist[i][j] < mincost)) {
					mincost = dist[i][j];
					u = j;
				}
			}

			if (mincost == INF) {
				break;
			}

			color[u] = 3;

			REP3(j, N) {
				if ((color[j] != 3) && (G[u][j] < INF)) {
					if (dist[i][u] + G[u][j] < dist[i][j]) {
						dist[i][j] = dist[i][u] + G[u][j];
						p[j] = u;
						color[j] = 2;
					}
				}
			}
		}

	}

	/*
	REP3(i, N) {
		REP3(j, N) {
			cout << i << " " << j << " " << dist[i][j] << endl;
  		}
	}
	*/

	int res,tmp;
	res = 0;

	REP(i, M) {
		tmp = 0;
		REP3(j, N) {
			if ((dist[j][b[i]] == dist[j][a[i]] + G[a[i]][b[i]]) && (j != b[i])) {
				++tmp;
			}
		}
		if (tmp == 0)++res;
	}
	
	cout << res << endl;

	int end;
	cin >> end;

	return 0;
}

Submission Info

Judge Result