AtCoder Beginner Contest 051 D - Candidates of No Shortest Paths

問題

http://abc051.contest.atcoder.jp/tasks/abc051_d

解法

Floyd-Warshall algorithmで各頂点間の最小移動距離を計算し, 得られた距離の行列をとします.
今, 辺端点, , 重みをとする辺が使われるかどうかを考えます. なら, 辺のみを使う経路がからまでの最短経路の集合の中に存在します. なら, を使った時点ですでに移動距離のコストがを超えてしまうことから, を使ってしまったら, その経路はからまでの最短経路とはなりません. よってなら任意の頂点間の最短経路において, が使われることはありません. 仮にが使われているとすると, その部分をより距離が短い部分に置き換えることができて, 経路の長さが最小であることに反します.
以上より全ての辺についてその端点間の最小距離と辺の重みを比較することで答えを得ることができます.

ソースコード

#include <iostream>
using namespace std;

const int MAX_N = 110;
const int MAX_M = 1010;
const int INF = (1 << 28);

struct Edge {
    int endpoint1;
    int endpoint2;
    int weight;

    Edge() {}
    Edge(int ep1, int ep2, int w)
        : endpoint1(ep1), endpoint2(ep2), weight(w) {}
};

int cost[MAX_N][MAX_N];
Edge edges[MAX_M];

int main() {
    int n, m;
    cin >> n >> m;

    // Floyd-Warshall algorithmのための初期化
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cost[i][j] = (i == j) ? 0 : INF;
        }
    }

    for (int m_i = 0; m_i < m; m_i++) {
        int a, b, c;
        cin >> a >> b >> c;

        a--; b--;
        edges[m_i] = Edge(a, b, c);
        edges[m_i] = Edge(b, a, c);

        cost[a][b] = min(cost[a][b], c);
        cost[b][a] = min(cost[b][a], c);
    }

    // Floyd-Warshall algorithm
    for (int k = 0; k < n; k++) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                cost[i][j] = min(cost[i][j], cost[i][k] + cost[k][j]);
            }
        }
    }

    int ans = 0;
    for (int m_i = 0; m_i < m; m_i++) {
        int ep1 = edges[m_i].endpoint1,
            ep2 = edges[m_i].endpoint2,
            w = edges[m_i].weight;
        if (cost[ep1][ep2] < w) {
            ans++;
        }
    }
    cout << ans << endl;

    return 0;
}

感想

試験期間中ですが, 現実逃避するために解きました.