blog.bouzuya.net

2023-05-15 マグにさよなら / 典型アルゴリズム問題集 E問題を解いた

お気に入りのマグを割ってしまった。1個ではなく手を滑らせて落としたところにもう1個があって2個同時に、だ。さようなら。

https://iris.to/note1a6y353a9d7ctyq3u6lxrxqm07dawxlmeldzzw36hawkfxnwjkswsd3xcxh

use proconio::input;

fn main() {
    input! {
        n: usize,
        m: usize,
        uvc: [(usize, usize, usize); m],
    }

    let inf = 1_usize << 60;
    let mut dist = vec![vec![inf; n]; n];
    for i in 0..n {
        dist[i][i] = 0;
    }
    for (u, v, c) in uvc {
        dist[u][v] = dist[u][v].min(c);
    }
    for k in 0..n {
        for i in 0..n {
            for j in 0..n {
                dist[i][j] = dist[i][j].min(dist[i][k] + dist[k][j]).min(inf);
            }
        }
    }
    let mut sum = 0_usize;
    for i in 0..n {
        for j in 0..n {
            sum += dist[i][j];
        }
    }
    let ans = sum;
    println!("{}", ans);
}

今日のコミット。