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