blog.bouzuya.net

2023-05-25 ガラス戸の修理 / PAST #1 L を解いた

ガラス戸の修理。お金が飛んでいった。

あと 2 問で PAST 本の問題が終わる。 PAST 上級本を買おうか。

neverthrow の ResultAsync を試している。

use dsu::Dsu;
use proconio::{input, marker::Usize1};

fn main() {
    input! {
        n: usize,
        m: usize,
        xyc: [(i64, i64, Usize1); n],
        capital_xyc: [(i64, i64, Usize1); m],
    }

    let mut ans = std::f64::MAX;
    for bits in 0_usize..1 << m {
        let n = n + bits.count_ones() as usize;
        let vertices = xyc
            .iter()
            .copied()
            .chain(
                (0..m)
                    .filter(|i| ((bits >> i) & 1) == 1)
                    .map(|i| capital_xyc[i]),
            )
            .collect::<Vec<(i64, i64, usize)>>();

        let mut edges = vec![];
        for (i, (x_i, y_i, c_i)) in vertices.iter().copied().enumerate() {
            for (j, (x_j, y_j, c_j)) in vertices.iter().copied().enumerate() {
                if i == j {
                    continue;
                }
                let cost = (((x_i - x_j).pow(2) + (y_i - y_j).pow(2)) as f64).sqrt();
                edges.push((i, j, cost * if c_i == c_j { 1_f64 } else { 10_f64 }));
            }
        }

        edges.sort_by(|(_, _, a), (_, _, b)| a.partial_cmp(b).unwrap());

        let mut sum = 0_f64;
        let mut dsu = Dsu::new(n);
        for (u, v, c) in edges {
            if dsu.same(u, v) {
                continue;
            }
            dsu.merge(u, v);
            sum += c;
        }

        ans = ans.min(sum);
    }
    println!("{}", ans);
}

// dsu

今日のコミット。