結果

問題 No.872 All Tree Path
ユーザー pod1pod1
提出日時 2019-09-06 23:44:46
言語 Rust
(1.77.0)
結果
AC  
実行時間 212 ms / 3,000 ms
コード長 1,054 bytes
コンパイル時間 812 ms
コンパイル使用メモリ 147,836 KB
実行使用メモリ 41,044 KB
最終ジャッジ日時 2023-09-07 02:55:12
合計ジャッジ時間 5,290 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 178 ms
22,808 KB
testcase_01 AC 183 ms
22,836 KB
testcase_02 AC 179 ms
22,820 KB
testcase_03 AC 85 ms
41,044 KB
testcase_04 AC 1 ms
4,376 KB
testcase_05 AC 212 ms
22,836 KB
testcase_06 AC 184 ms
22,856 KB
testcase_07 AC 178 ms
22,836 KB
testcase_08 AC 12 ms
4,384 KB
testcase_09 AC 11 ms
4,380 KB
testcase_10 AC 10 ms
4,376 KB
testcase_11 AC 11 ms
4,380 KB
testcase_12 AC 12 ms
4,376 KB
testcase_13 AC 1 ms
4,380 KB
testcase_14 AC 1 ms
4,376 KB
testcase_15 AC 1 ms
4,376 KB
testcase_16 AC 1 ms
4,380 KB
testcase_17 AC 1 ms
4,376 KB
testcase_18 AC 1 ms
4,380 KB
testcase_19 AC 1 ms
4,380 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
warning: unused variable: `dist`
  --> 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

warning: 1 warning emitted

ソースコード

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