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;
}