AtCoder Begineer Contest 051 D - Candidates of No Shortest Paths

June 14, 2021

ワーシャルフロイト法で全ての2頂点間の最短距離を求めた後、隣接する2頂点の辺のうち、2頂点の最短距離が辺の重みと異なる辺を数えれば通る。

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

const ll INF = 100000000000ll;

int main() {
    int n, m;
    cin >> n >> m;
    vector<ll> a(m), b(m), c(m);
    for(int i = 0; i < m; i++) {
        cin >> a[i] >> b[i] >> c[i];
        a[i]--;
        b[i]--;
    }
    vector<vector<ll>> d(n, vector<ll>(n, INF));
    for(int i = 0; i < m; i++) {
        d[a[i]][b[i]] = 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 = 0;
	for(int i=0;i<m;i++) {
		if(d[a[i]][b[i]] != c[i])
			ans++;
	}
	cout << ans << endl;
    return 0;
}