Rustコトハジメ

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

【ABC073-D joisino's travel】Rustでdo-whileする方法とnext_permutationの注意

方針自体は簡単。しかしテストケースが1つだけ通らない実装ハメに気づくために5時間くらい悩みました。途中、AtCoderAWSのダウンによって動かなくなったため、やきもきしました。

D - joisino's travel

問題

辺にコストが定義されたグラフN(<=200)が与えられる。与えられたR(<=8)個の点をすべて通る最短距離を求めよ。

方針

まずワシャフロで全点最短距離を求めます。3乗オーダーですが、200なのでいける。

あとは、Rの順列すべて(8!)について、全探索します。

実装

froidではなくてfloydのようです・・・。registみたいですね。

fn solve() {
    input! {
        N:usize,M:usize,R:usize,
        r:[(usize);R],
        ABC:[(usize,usize,i64);M],
    }
    let mut inf: i64 = 1<<50;
    let mut g = vec![vec![inf;N];N];
    for i in 0..N {
        g[i][i] = 0;
    }
    for (a,b,c) in ABC {
        g[a-1][b-1] = c;
        g[b-1][a-1] = c;
    }
    warshal_froid(&mut g);

    let mut minv = inf;
    let mut r = r;
    r.sort();
    loop {
        // dbg!(&r);
        let mut sum = 0;
        assert!(r.len() >= 2);
        for i in 0..r.len()-1 {
            let (u,v) = (r[i]-1, r[i+1]-1);
            assert!(g[u][v] == g[v][u]);
            sum += g[u][v];
        }
        minv = min(minv,sum);
        if !r.next_permutation() {
            break;
        }
    }
    println!("{}",minv);
}

考察

do-whileの書き方

Rustにはdo-while構文はありませんが、

do {
    do_something();
} while (test())

は、

loop {
    do_something();
    if !test() { break; }
}

で書けます。

next_permutationの注意点

hatooさんのライブラリからC++のnext_permutationのRustポートをもらって盲目的に使いましたが、配列は初期状態でソートされている必要があるということを知らなかったため、ハマりました。5時間もハマりましたが、本番コンテストでミスることがなくなったので粘った甲斐がありました。