ABC257-D O(N^4)

O(N^3) → O(N^4) に訂正しました。

---

想定解

$ $
$S$を決めると、頂点間の移動について数値ではなく可能/不可能のbool値に還元できる。ワーシャルフロイド法でいずれかの頂点を始点として全頂点に到達可能かどうか、$O(N^3)$で求まる。あとは条件を満たす$S$の最小値を2分探索で求める。$O(N^3logS_{max})$で求まる。
$ $

---

コンテスト中に試みたこと

$ $
コンテスト中に試みたこと
頂点間の移動コストは、$dist(x,y) / P_x$。辺のない状態から出発して、値の小さい方から辺を追加していく。いずれかの頂点から全頂点に到達可能になれば、最後にみた$⌈ dist(x,y) / P_x ⌉$が求める$S$。
時間中は全ての頂点からダイクストラ法で全域木を求め、最後に採用した辺についての$⌈ dist(x,y) / P_x ⌉$を解としたが、TLEとなった。WAではないがおそらく嘘解法
$ $

$ $
想定解は納得いくものではあるが、頂点間の移動コストの小さい順から試すというアプローチも捨てがたく、なんとかならないものか。
頂点間の移動コストが対称であれば、無向グラフの連結性の問題となり、Union-Findのデータ構造が利用できる。しかし、今回はうまくいきそうにない。
$ $

---

ワーシャルフロイド法を利用

$ $
想定解にも登場するワーシャルフロイド法は有向グラフの全頂点間最短距離を$O(|V|^3)$で求めるアルゴリズム。

wf.rs

for k in 0..n {
    for i in 0..n {
        for j in 0..n {
            dist[i][j] = dist[i][j].min(dist[i][k] + dist[k][j]);
        }
    }
} 

dist[i][j] = ... は、「新たに使用できる頂点kを使用する場合と使用しない場合を考え、全頂点間の距離を更新(緩和)する」処理。詳しくはけんちょん本を。

この考えを利用し、「新たに使用できる辺を使用する場合と使用しない場合を考え、全頂点間の距離を緩和する」。

AC.rs

fn main() {

    (中略)

    // amは隣接行列。bool値で管理
    let mut am = vec![vec![false; n]; n];
    for i in 0..n { am[i][i] = true; }

    // edgesは辺のリストで、(移動コスト, 始点, 終点)が昇順で格納されている
    for (r, k, l) in edges {

        // 辺の数はN^2程度あるが、木ができれば終了するので実際の処理はN回程度。
        // ↑有向グラフなので最大N^2オーダーありそうです
        if am[k][l] { continue; }
        am[k][l] = true;

        // 辺k->lの情報を加味し、全頂点間の連結情報を更新する
        for i in 0..n {
            for j in 0..n {
                am[i][j] |= am[i][k] && am[l][j];
            }
        }

        // ある頂点を始点とし、全ての頂点に到達可能となれば打ち切り
        if am.iter().any(|v| v.iter().all(|&x| x == true )) {
            // ⌈dist(x,y) / Px⌉ が求める解
            println!("{}", r.ceil());
            break;
        }
    }
}

時間計算量は、$O(|E|log|E|+|V|^2|E|) = O(N^2log(N^2)+N^4) = O(N^4)$。