結果

問題 No.872 All Tree Path
ユーザー pod1
提出日時 2019-09-06 23:44:46
言語 Rust
(1.83.0 + proconio)
結果
AC  
実行時間 186 ms / 3,000 ms
コード長 1,054 bytes
コンパイル時間 15,072 ms
コンパイル使用メモリ 383,996 KB
実行使用メモリ 41,088 KB
最終ジャッジ日時 2024-06-24 21:36:35
合計ジャッジ時間 16,098 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 18
権限があれば一括ダウンロードができます
コンパイルメッセージ
warning: unused variable: `dist`
  --> src/main.rs:25:7
   |
25 |   let dist = dfs(&g, &mut visit, 0,&mut ans);
   |       ^^^^ help: if this is intentional, prefix it with an underscore: `_dist`
   |
   = note: `#[warn(unused_variables)]` on by default

ソースコード

diff # 

use std::vec::Vec;


fn read<T: std::str::FromStr>() -> T {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    s.trim().parse().ok().unwrap()
}

fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read::<String>().split_whitespace().map(|e| e.parse().ok().unwrap()).collect()
}


fn main() {
  let n: usize = read();
  let mut g: Vec<Vec<(usize, usize)>> = vec![Vec::new(); n];
  for _ in 0..n-1 {
    let t: Vec<usize> = read_vec();
    g[t[0] - 1].push((t[1] - 1, t[2]));
    g[t[1] - 1].push((t[0] - 1, t[2]));
  }
  let mut visit = vec![false; n];
  let mut ans = 0;
  let dist = dfs(&g, &mut visit, 0,&mut ans);
  println!("{}", 2 * ans);
}

fn dfs(g: &Vec<Vec<(usize, usize)>>, visit: &mut Vec<bool>, now: usize, ans: &mut usize) -> usize {
  visit[now] = true;
  let n: usize = g.len();
  let mut res = 0;
  for &(node, cost) in &g[now] {
    if visit[node] { continue; }
    // 子ノードの個数
    let count = dfs(g, visit, node, ans);
    *ans += cost * count * (n - count);
    res += count;
  }

  res + 1
}
0