Rustコトハジメ

プログラミング言語Rustと競プロに関する情報をお届けします。

【ABC051-D Candidates of No Shortest Paths】ワシャフロの理解

D - Candidates of No Shortest Paths

問題

無向連結グラフが与えられる。その中で、どの最短路にも含まれていない辺の数を求めなさい。最短経路が計算出来る原理の理解を求められる問題。

方針

ワシャフロで全点最短路を計算して、ある辺(i,j)について、

dp[s][i] + d[i][j] + dp[j][t] = dp[s][t]

となるようなs,tが見つかるなら、i,jは最短路として使われていることになる。

誤った方針

私の初期解答は猿だった。

ある2点s,tについて、sから出る辺eがその最短路として使われているかどうかチェックする

という方針でやったが、当然誤りで、それだと、最短路の中間あたりで使われるケースが抜け落ちてしまう。

二度とミスるなカスが。

実装

fn solve() {
    input! {
        N: usize, M: usize,
        ABD: [(usize,usize,i64); M],
    }
    let inf = 1<<40;
    let mut h = HashSet::new();
    let mut es = vec![];
    let mut g = vec![vec![inf; N]; N];
    for i in 0..N {
        g[i][i] = 0;
    }
    for (a,b,d) in ABD {
        g[a-1][b-1] = d;
        g[b-1][a-1] = d;

        let (x,y) = asc(a-1,b-1);
        h.insert(asc(x,y));
        es.push((x,y,d));
    }
    // dbg!(&g);
    warshal_froid(&mut g); // N^3

    for (x,y,d) in es {
        for i in 0..N {
            for j in 0..N {
                if i==j { continue; }
                if g[i][x] + d + g[y][j] == g[i][j] {
                    h.remove(&(x,y));
                }
            }
        }
    }
    // dbg!(&dp);
    println!("{}", h.len());
}