ABC051: D - Candidates of No Shortest Paths
問題
D - Candidates of No Shortest Paths
解説
どこの最短距離にも含まれない辺となる条件は、辺のコストが端点同士の最短距離となっていないことである。 ワーシャルフロイドで全点間の最短距離を求め、各辺についてのコストと比較すれば良い。
自分の思考過程としては、題意を理解する -> ワーシャルフロイドが使える -> 辺が含まれるかという状態の探索的な思考より、漸化式的・差分的な思考のほうが単純そう -> 差分的の思考から最短距離を小さいスケールで捉える方が良さそう -> そもそも各辺に着目するだけで良い。
int G[101][101]; int raw[101][101]; vector<pair<int, int>> vs; int main() { int N, M; cin >> N >> M; rep(i, N) rep(j, N) G[i][j] = raw[i][j] = i == j ? 0 : inf; rep(i, M) { int a, b, c; cin >> a >> b >> c; a--, b--; G[a][b] = G[b][a] = c; raw[a][b] = raw[b][a] = c; vs.emplace_back(a, b); } rep(k, N) rep(i, N) rep(j, N) { minimize(G[i][j], G[i][k] + G[k][j]); } int count = 0; for (auto e: vs) { count += G[e.first][e.second] < raw[e.first][e.second]; } cout << count << endl; }