AtCoder Beginner Contest 051: Candidates of No Shortest Paths

問題

問題文

https://atcoder.jp/contests/abc051/tasks/abc051_d

問題概要

頂点数 N, 辺の数 M の重み付き無向グラフが与えられる.

ただし, このグラフは自己ループと二重辺をもたず, 連結であるものとする.

任意の 2頂点間のどの最短経路にも含まれない辺の数を求めよ.

制約

$2 \leqq N \leqq 100$
$N-1 \leqq M \leqq min(N(N-1)/2, 1000)$

解答例

指針

辺 e = (u, v) が最短経路に含まれるかどうかを u, v の最短経路が辺 e のコストと一致しているかで判定

解説

解法1

次のようなグラフを例に考える.

f:id:kira000:20190426065752p:plain

赤で示した辺 e = (u, v) が, ある異なる2点間 s, g の最短経路に含まれるのであれば,

(sからgの最短経路) = (s から u の最短経路) + (e のコスト) + (v から g の最短経路)

(sからgの最短経路) = (s から v の最短経路) + (e のコスト) + (u から g の最短経路)

のいずれかが必ず成立するはずである.

各辺について s, g をそれぞれ全探索し, 上記の式が成り立つようなものが存在するかを調べれば良いので, O(M*N²) でこの問題を解くことが出来た.

(全点対間の最短経路は Floyd-Warshall で O(N³) で求めることが出来る.)

C++ による実装例

// submission: https://atcoder.jp/contests/abc051/submissions/5123019
// Language: C++14 (GCC 5.4.1)
// Time: 31 ms
// Memoly: 256 KB

#include <iostream>
#include <algorithm>

using namespace std;

const int INF = (int)1e8;

int main() {
    int n, m, d[102][102]; 
    int a[1003], b[1003], c[1003];

    cin >> n >> m;

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            d[i][j] = INF;
        }
        d[i][i] = 0;
    }

    for (int i = 0; i < m; i++) {
        cin >> a[i] >> b[i] >> c[i];
        a[i]--; b[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++) {
        bool is_valid = false;

        for (int start = 0; start < n; start++) {
            for (int goal = 0; goal < n; goal++) {
                if (start == goal) { continue; }
                if ( d[start][goal] == d[start][a[i]] + c[i] + d[b[i]][goal]
                    || d[start][goal] == d[start][b[i]] + c[i] + d[a[i]][goal] ) {
                    is_valid = true;
                }
            }
        }
        if (!is_valid) { ans++; }
    }
    cout << ans << endl;
    return 0;
}

解法2

f:id:kira000:20190426065752p:plain

もし, u, v 間の最短経路が u から v を直接つなぐ辺 e を一度だけ通る経路であれば, 辺 e は (u, v) の最短経路なので当然, 最短経路に含まれる辺となる.

逆に, u, v 間の最短経路が u から v を直接つなぐ辺 e を一度だけ通る経路でないのなら, 辺 e はどの 2 点間の最短経路にも含まれない.

なぜなら, u, v 間を最短経路のパスに含むとすると, 直接辺 e = (u, v) を通るよりも, 少ないコストで u, v 間を移動できるルートが存在するから辺 e は最短経路として使われることは決してないからである.

したがって, 各辺 (a, b) について (a[i], b[i] の最短経路のコスト) = c[i] となっているかを調べれば良い.

この場合の計算量は Floid-Warshall の部分が支配的となり O(N³).

C++ による実装例

// submission: https://atcoder.jp/contests/abc051/submissions/5123046
// Language: C++14 (GCC 5.4.1)
// Time: 3 ms
// Memoly: 256 KB


#include <iostream>
#include <algorithm>

using namespace std;

const int INF = (int)1e8;

int main() {
    int n, m, d[102][102]; 
    int a[1003], b[1003], c[1003];

    cin >> n >> m;

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            d[i][j] = INF;
        }
        d[i][i] = 0;
    }

    for (int i = 0; i < m; i++) {
        cin >> a[i] >> b[i] >> c[i];
        a[i]--; b[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;
}