$ $重み付き無向グラフがある。全頂点間の最短経路を求めたとき、最短経路に一度も含まれない辺が幾つあるか。
頂点数 $N≤100$ 、辺の数 $M≤1000$。
１日かけて解けた。
ワーシャルフロイド法
$ $
$N^3 ≤ 10^6$ であるので、ワーシャルフロイドが使える。
ワーシャルフロイドで３重ループを回せば、任意の２頂点間の距離 $dist(a,b)$ がもとまる。
$dist(a_i,b_i)=c_i$であれば、２頂点を直接結ぶ辺が $(a_i,b_i)$ 間の最短経路となることができる。
$ dist(a_i,b_i) < c_i $の場合、２頂点を直接結ぶ辺は最短経路に含まれないことはわかる。しかし、一度も含まれないかどうかはわからない。
ワーシャルフロイドで出てくる緩和式 $ dist(i,j) → min(dist(i,j), dist(i,k)+dist(k,j)) $ に何か仕掛けをすれば、直接結ぶ辺が使用されるかされないかが判定できそう。でもそれをまとめる方法が思いつかない。
辺を一つ削除してワーシャルフロイドして、全頂点間の距離が削除前と変わらなければその辺は不要ということになる。でも最短経路が二つ存在する場合もあり、その時はその辺は「不要」ではあるが「使うことはできる」ので「最短経路に含まれない」とは言えない。
ダイクストラ法
$ $
ダイクストラ法は、priority queue (RustではBinaryHeap)を利用して1つの頂点から全頂点までの距離を求めることができる。
各辺の距離が全て1だとBFSと同じこと。全て非負整数であれば、距離nの辺を距離1の辺の連なりに分解すればBFSと同じこと。
priority queueのpush, popが $O(logN)$ であり、それを辺の数だけ繰り返すので始点1つにつき $O(MlogN)$ 。全頂点間だと公式解説のとおりで $O(NMlogN)$ 。
考察する
$ $頂点 $s$ から頂点 $t$ までの最短経路に辺 $(a_i,b_i)$ が使われるか。
辺 $(a_i,b_i)$ を削除してダイクストラして、距離が変わるか変わらないかというのは、前述の通りその辺が使われるか使われないかとは対応しない。
「ギリギリを考える」と、糸口が見つかった。
$ $辺 $(a_i,b_i)$ を削除した上で頂点 $a_i$ から頂点 $b_i$ までの距離 $d$ を求め、削除した辺の距離 $c_i$と比較する。
・$ d < c_i $のとき → 辺 $(a_i,b_i)$ の代わりに常に距離 $d$ の最短経路が使われるので、その辺は最短経路に含まれない。
・$ d > c_i $のとき → その辺は頂点 $a_i$ から $b_i$ までの最短経路に含まれる。
・$ d = c_i $のとき → その辺は頂点 $a_i$ から $b_i$ までの最短経路(の一つ)に含まれる。
ダイクストラ法での解法
use std::collections::BinaryHeap;
use std::cmp::Reverse;
use proconio::{input, marker::Usize1};
fn main() {
// 入力
input!{
n: usize, m: usize,
abc: [(Usize1, Usize1, usize); m],
}
// 重み付き隣接リストを構成
let mut to = vec![vec![]; n];
for &(a, b, c) in &abc {
to[a].push( (b,c) );
to[b].push( (a,c) );
}
// 使われない辺をカウントする
let mut ans = 0;
// 一つの辺を削除した上で、aからbへの最短距離を求める
for &(a, b, c) in &abc {
let mut dist = vec![None; n];
let mut pq = BinaryHeap::new();
// BinaryHeapは降順にpopするので、Reverseでラップして比較関数を逆転させて昇順にする
pq.push((Reverse(0), a));
// Rustで競プロしてるのはwhile let文があるから
while let Some((Reverse(d), x)) = pq.pop() {
// 距離が既に代入されていればそれが最小なのでスキップ
if dist[x].is_some() { continue; }
// aからの距離dを代入
dist[x] = Some(d);
// 終点bに到達していれば d < c かどうかで判別してansに加算し、打ち切る
if x == b {
if d < c { ans += 1; }
break;
}
for &(y,c) in &to[x] {
// 辺(a,b)はスキップ
if x == a && y == b || x == b && y == a { continue; }
// 距離が既に代入されていればそれが最短なのでスキップ
if dist[y].is_some() { continue; }
// dist(a,x)+dist(x,y)をdist(a,y)の最短距離候補としてプッシュ
pq.push((Reverse(d+c), y));
}
}
}
// 出力
println!("{}", ans);
}
$O(NMlogN)$ であり、十分高速に動作します。
ワーシャルフロイド法での解法
$ $全頂点間で最短距離を求めておく ($dist$) 。
$ $頂点 $s$ と頂点 $t$ を結ぶのに、辺 $(a_i,b_i)$ を強制的に使うことを考える。
この時の最短距離 $d$ は、$d = min(;dist(s,a_i)+c_i+dist(b_i,t),, ;dist(s,b_i)+c_i+dist(a_i,t);)$。
これと $dist(s,t) $を比較。
$ $
・ $d < dist(s,t)$ は、 $dist(s,t)$ が最短距離であることに反するのであり得ない。$unreachable!()$
・ $d = dist(s,t)$ は、辺 $(a_i,b_i)$ が $s$ と $t$ の最短経路に含まれることを意味する。
・ $d > dist(s,t)$ は、辺 $(a_i,b_i)$ が $s$ と $t$ の最短経路に含まれないことを意味する。
$ $
つまり、全ての頂点の組み合わせ $(s,t)$ について
$$
min(;dist(s,a_i)+c_i+dist(b_i,t),, ;dist(s,b_i)+c_i+dist(a_i,t);) > dist(s,t)
$$
を満たすような $i$ をカウントすれば、それが答えになる。 上の判別式は
$$
dist(s,a_i)+c_i+dist(b_i,t) > dist(s,t) \quad ∧ \quad dist(s,b_i)+c_i+dist(a_i,t);) > dist(s,t)
$$
と分解でき、$s$と$t$を入れ替えたものと同値なので、$s$,$t$全操作前提なら片方だけでよい。
$$
dist(s,a_i)+c_i+dist(b_i,t) > dist(s,t)
$$
$ $コードは公式解説のようになる。
時間計算量は$O(N^3+MN^2)$。制約より$N-1≤M$がわかるので$O(MN^2)$。
ワーシャルフロイド法での解法(もっと簡単に)
$ $全頂点間で距離($dist$)を求めておく。
頂点 $a_i$ と頂点 $b_i$ を直接結ぶ辺の距離 $c_i$ と $dist(a_i,b_i)$ を比較する。
・ $c_i < dist(a_i,b_i)$ は、 $dist(a_i,b_i)$ が最短距離であることに反するのであり得ない。
・ $c_i = dist(a_i,b_i)$ は、辺 $(a_i,b_i)$ が $a_i$ と $b_i$ の最短経路に含まれることを意味する。
・ $c_i > dist(a_i,b_i)$ は、考察する。
$c_i > dist(a_i,b_i)$ かつ $s$ と $t$の最短経路が辺 $(a_i,b_i)$ を含むなら、
$dist(s,t) = dist(s,a_i)+dist(a_i,b_i)+dist(b_i,t)$ が成り立つ。
ところが、$c_i > dist(a_i,b_i)$であるので $a_i$ と $b_i$の最短経路は辺 $(a_i,b_i)$ とは別に存在する。$s$ と $t$の最短経路が辺 $(a_i,b_i)$ を含むという前提であるが、辺 $(a_i,b_i)$ をもっと短い経路に置き換えることで $dist(s,t)$ をさらに小さくする事が可能であり、これは $dist(s,t)$ が最短距離であることに矛盾。
$ $
よって、$c_i > dist(a_i,b_i)$ のとき、$s$ と $t$の最短経路は辺 $(a_i,b_i)$ を含まない。
つまりワーシャルフロイドでもダイクストラでも $dist(a_i, b_i)$ を全て求めて、$c_i$ よりも小さなものをカウントすればよかった。
use proconio::{input, marker::Usize1};
fn main() {
// 入力
input!{
n: usize, m: usize,
abc: [(Usize1, Usize1, usize); m],
}
// 重み付き隣接行列を構成
let mut dist = vec![vec![None; n]; n];
for a in 0..n {
dist[a][a] = Some(0);
}
for &(a, b, c) in &abc {
dist[a][b] = Some(c);
dist[b][a] = Some(c);
}
// ワーシャルフロイド
for k in 0..n {
for i in 0..n {
for j in 0..n {
if let (Some(y), Some(z)) = (dist[i][k], dist[k][j]) {
if let Some(x) = dist[i][j] {
dist[i][j] = Some(x.min(y+z));
} else {
dist[i][j] = Some(y+z);
}
}
}
}
}
// 使われない辺をカウントする
let mut ans = 0;
// (a,b)の最短距離がcより短ければその辺は不要
for &(a, b, c) in &abc {
if dist[a][b] < Some(c) { ans += 1; }
}
// 出力
println!("{}", ans);
}
Take Home Message
実装できるところまで考察がすすめば十分であるが、
もっと考察することで実装がもっと簡単になる場合もある。