Submission #1609927

---

Source Code Expand

#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
int INF = 1e9;
int MOD = 1e9+7;
ll dist[100][100];
bool used[100][100];
main(){
    fill(dist[0],dist[100],INF);
    for(int i = 0;i < 100;i++)dist[i][i] = 0;
    int N,M;
    cin >> N >> M;
    for(int i = 0;i < M;i++){
        int a,b,c;
        cin >> a >> b >> c;
        a--;b--;
        dist[a][b] = dist[b][a] = c;
        used[a][b] = used[b][a] = 1;
    }
    for(int i = 0;i < N;i++){
        for(int j = 0;j < N;j++){
            for(int k = 0;k < N;k++){
                if(dist[j][k] > dist[j][i] + dist[i][k]){
                    dist[j][k] = dist[j][j] + dist[i][k];
                    used[j][k] = used[k][j] = 0;
                }
            }
        }
    }
    int cnt = 0;
    for(int i = 0;i < N;i++)for(int j = 0;j < N;j++)cnt += used[i][j];
    cout << M - cnt/2 << endl;
}

Submission Info

Judge Result