Sightseeing Tour の解説

ワーシャルフロイドで各頂点の最短距離をO(N^3)で求められる。

あとは、各頂点をどの順番でどの向きで移動するかを全探索する。 k <= 5なので、これは最大 5! * 2^5 = 3,840通りしかないので、クエリ <= 3000であれば探索可能

fn main() {
    input! {
        n: usize,
        m: usize,
        uvt: [(Usize1, Usize1, usize); m],
        q: usize
    }
    let mut table = {
        let mut table = vec![vec![usize::MAX; n]; n];
        for i in 0..n {
            table[i][i] = 0;
        }
        for &(u, v, t) in uvt.iter() {
            let now = table[u][v];
            table[u][v] = min(now, t);
            table[v][u] = min(now, t);
        }
        for k in 0..n {
            for i in 0..n {
                for j in 0..n {
                    let next = table[i][k].saturating_add(table[k][j]);
                    table[i][j].chmin(next);
                }
            }
        }
        table
    };
    for _ in 0..q {
        input! {
            k: usize,
            b: [Usize1; k]
        }
        let mut ans = usize::MAX;
        for p in b.iter().permutations(k) {
            for pp in (0..=1).product_repeat(k) {
                let mut now = 0;
                let mut cur = 0;
                for i in 0..k {
                    let &next = p[i];
                    let (u, v, t) = uvt[next];
                    let flg = pp[i] == 0;
                    let uu = if flg { u } else { v };
                    let vv = if flg { v } else { u };
                    cur += table[now][uu];
                    cur += t;
                    now = vv;
                }
                cur += table[now][n - 1];
                ans = min(ans, cur);
            }
        }
        println!("{}", ans);
    }
}