Submission #1070687

---

Source Code Expand

#include <iostream>
using namespace std;


int main() {
    const int inf = 100000000;
    
    int n,m;
    cin >> n >> m;
    
    //入力データ用の変数
    int a[1000],b[1000],c[1000];
    
    //データの入力
    for(int i = 0; i < m; ++i){
        cin >> a[i] >> b[i] >> c[i];
        a[i]--,b[i]--; //配列のインデックスと合わせるため
    }
    
    //アルゴリズム用の変数
    int dist[100][100];
    
    //アルゴリズム用の初期化１
    for(int i = 0; i < n; ++i){
        for(int j = 0; j < n; ++j){
            if(i==j)
                dist[i][j]=0;
            else
                dist[i][j]=inf;
        }
    }
    
    //アルゴリズム用の初期化２（辺のある場合は更新）
    for(int i = 0; i < m; ++i){
        dist[a[i]][b[i]]=min(dist[a[i]][b[i]],c[i]);
        dist[b[i]][a[i]]=min(dist[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){
                dist[i][j]=min(dist[i][j],dist[i][k]+dist[k][j]);
            }
        }
    }
    
    //最短経路でない辺を数え上げ（最短経路辺のユニオンを数え上げ）
    int ans=m;
    for(int i = 0; i < m; ++i){
        bool shortest=false;
        for(int j = 0; j < n; ++j){
            for (int k = 0; k < n; ++k) {
                if(dist[j][a[i]]+c[i]+dist[b[i]][k]==dist[j][k]) shortest=true;
            }
        }
        if(shortest==true){
            ans=ans-1;
        }
    }
    
    cout << ans << endl;
    
    
    return 0;
}

Submission Info

Judge Result