Rustコトハジメ

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

【TTPC2019-F Road Construction】グラフの変形

コンテスト中に解けなかったので解いておきます。

F - Road Construction

問題

コストつきのグラフが与えられる。これらの辺は最初、有効になっていない。このうち、いずれかの辺を有効化して、wからx、yからzの両方が通るようにしたい。最小のコストはいくらか?

方針

左と右にsとtを用意して、sからtへのコスト問題に帰着させたい。x,w,y,zから各点への最短距離はダイクストラで計算が間に合う。

そのあと、グラフを以下のように変形する。

f:id:akiradeveloper529:20190902200144j:plain

辺を共有する場合は赤のようになる。この時、共有する始点までの、終点からそれぞれのゴールまでの距離の和は、それぞれの個別の最短路の合計値で置き換えることが出来る。従って、そのような辺を追加した上で最短路問題を解くことに帰着出来る。

辺を共有しない場合に最短な可能性もあるので、これは青の部分の合計を加算する。

赤と青のうち小さい方が答えとなる。

実装

177msだった。

fn solve() {
    input!{
        N:usize,M:usize,
        A:usize,B:usize,C:usize,D:usize,
        CST:[(i64,usize,usize);M]
    } 
    let mut g=vec![vec![];N+2];
    let mut g_rev=vec![vec![];N+2];
    for &e in &CST {
        g[e.1].push(Edge { to: e.2, cost: e.0 });
        g_rev[e.2].push(Edge { to: e.1, cost: e.0 });
    }
    let from_A = dijkstra_heap(&g, A, std::i64::MAX);
    let from_C = dijkstra_heap(&g, C, std::i64::MAX);
    let from_B = dijkstra_heap(&g_rev, B, std::i64::MAX);
    let from_D = dijkstra_heap(&g_rev, D, std::i64::MAX);

    let dpA = dijkstra_heap(&g, A, std::i64::MAX);
    let dpC = dijkstra_heap(&g, C, std::i64::MAX);
    // dbg!(&dpA, &dpC);

    for i in 1..N+1 {
        if from_A[i] == std::i64::MAX || from_C[i] == std::i64::MAX { continue; }
        g[0].push(Edge { to: i, cost: from_A[i]+from_C[i]});
    }
    for i in 1..N+1 {
        if from_B[i] == std::i64::MAX || from_D[i] == std::i64::MAX { continue; }
        g[i].push(Edge { to: N+1, cost: from_B[i]+from_D[i]});
    }
    // dbg!(&g);

    let dp = dijkstra_heap(&g, 0, std::i64::MAX);
    // dbg!(&dp);

    let sumdist = if dpA[B] == std::i64::MAX || dpC[D] == std::i64::MAX {
        std::i64::MAX
    } else { dpA[B]+dpC[D] };
    let minv = min(sumdist, dp[N+1]);
    if minv == std::i64::MAX {
        println!("Impossible");
    } else {
        println!("{}", minv);
    }
}

考察

答えが持っている性質から考えるというのは問題を解く時の一般的な考え方。グラフの場合、グラフの形状自体を決めつけてからそれ以外を省くみたいなケースが多いように思う。