#634654 (Rust) No.1442 I-wate Shortest Path Problem

• 問題: No.1442 I-wate Shortest Path Problem
• ユーザー: akakimidori
• 提出日時: 2021-03-26 22:26:30
• 言語: Rust (1.83.0 + proconio)
• 結果: AC
• 実行時間: 616 ms / 3,000 ms
• コード長: 7,403 bytes
• コンパイル時間: 15,590 ms
• コンパイル使用メモリ: 377,320 KB
• 実行使用メモリ: 35,256 KB
• 最終ジャッジ日時: 2024-11-28 23:58:55
• 合計ジャッジ時間: 21,379 ms
• ジャッジサーバーID （参考情報）: judge1 / judge4

ファイルパターン	結果
sample	AC * 2
other	AC * 25

コンパイルメッセージ

warning: method `parent` is never used
  --> src/main.rs:96:8
   |
10 | impl LCA {
   | -------- method in this implementation
...
96 |     fn parent(&self, v: usize) -> Option<usize> {
   |        ^^^^^^
   |
   = note: `#[warn(dead_code)]` on by default

ソースコード

// ---------- begin Lowest Common Ancestor ----------
struct LCA {
    graph: Vec<Vec<usize>>,
    parent: Vec<usize>,
    path_root: Vec<usize>,
    path_parent: Vec<usize>,
    index: Vec<usize>
}

impl LCA {
    fn new(n: usize) -> Self {
        LCA {
            graph: vec![vec![]; n],
            parent: vec![],
            path_root: vec![],
            path_parent: vec![],
            index: vec![],
        }
    }
    fn add_edge(&mut self, a: usize, b: usize) {
        assert!(a != b && a < self.graph.len() && b < self.graph.len());
        self.graph[a].push(b);
        self.graph[b].push(a);
    }
    fn build(&mut self, root: usize) {
        let n = self.graph.len();
        assert!(root < n);
        let mut parent = vec![root; n];
        let mut q = vec![root];
        let graph = &mut self.graph;
        for i in 0..n {
            let v = q[i];
            let p = parent[v];
            let child = &mut graph[v];
            if let Some(k) = child.iter().position(|u| *u == p) {
                child.swap_remove(k);
            }
            for &u in child.iter() {
                parent[u] = v;
                q.push(u);
            }
        }
        let mut size = vec![1; n];
        for &v in q.iter().rev() {
            if graph[v].is_empty() {
                continue;
            }
            let mut max = (0, 0);
            for (i, &u) in graph[v].iter().enumerate() {
                size[v] += size[u];
                if size[u] > max.0 {
                    max = (size[u], i);
                }
            }
            graph[v].swap(0, max.1);
        }
        let mut path_root = vec![root; n];
        let mut path_parent = vec![root; n];
        let mut index = vec![n; n];
        let mut stack = vec![root];
        let mut k = 0;
        while let Some(v) = stack.pop() {
            index[v] = k;
            k += 1;
            if graph[v].is_empty() {
                continue;
            }
            for &u in graph[v].iter().skip(1) {
                path_root[u] = u;
                path_parent[u] = v;
                stack.push(u);
            }
            let u = graph[v][0];
            path_root[u] = path_root[v];
            path_parent[u] = path_parent[v];
            stack.push(u);
        }
        self.parent = parent;
        self.path_root = path_root;
        self.path_parent = path_parent;
        self.index = index;
    }
    fn query(&self, mut a: usize, mut b: usize) -> usize {
        let path = &self.path_root;
        let parent = &self.path_parent;
        let index = &self.index;
        while path[a] != path[b] {
            if index[a] < index[b] {
                b = parent[b];
            } else {
                a = parent[a];
            }
        }
        if index[a] < index[b] {a} else {b}
    }
    fn parent(&self, v: usize) -> Option<usize> {
        let p = self.parent[v];
        if p == v {
            None
        } else {
            Some(p)
        }
    }
}
// ---------- end Lowest Common Ancestor ----------
// ---------- begin chmin, chmax ----------
pub trait ChangeMinMax {
    fn chmin(&mut self, x: Self) -> bool;
    fn chmax(&mut self, x: Self) -> bool;
}

impl<T: PartialOrd> ChangeMinMax for T {
    fn chmin(&mut self, x: Self) -> bool {
        *self > x && {
            *self = x;
            true
        }
    }
    fn chmax(&mut self, x: Self) -> bool {
        *self < x && {
            *self = x;
            true
        }
    }
}
// ---------- end chmin, chmax ----------
// ---------- begin scannner ----------
#[allow(dead_code)]
mod scanner {
    use std::str::FromStr;
    pub struct Scanner<'a> {
        it: std::str::SplitWhitespace<'a>,
    }
    impl<'a> Scanner<'a> {
        pub fn new(s: &'a String) -> Scanner<'a> {
            Scanner {
                it: s.split_whitespace(),
            }
        }
        pub fn next<T: FromStr>(&mut self) -> T {
            self.it.next().unwrap().parse::<T>().ok().unwrap()
        }
        pub fn next_bytes(&mut self) -> Vec<u8> {
            self.it.next().unwrap().bytes().collect()
        }
        pub fn next_chars(&mut self) -> Vec<char> {
            self.it.next().unwrap().chars().collect()
        }
        pub fn next_vec<T: FromStr>(&mut self, len: usize) -> Vec<T> {
            (0..len).map(|_| self.next()).collect()
        }
    }
}
// ---------- end scannner ----------

use std::io::Write;

fn main() {
    use std::io::Read;
    let mut s = String::new();
    std::io::stdin().read_to_string(&mut s).unwrap();
    let mut sc = scanner::Scanner::new(&s);
    let out = std::io::stdout();
    let mut out = std::io::BufWriter::new(out.lock());
    run(&mut sc, &mut out);
}

fn run<W: Write>(sc: &mut scanner::Scanner, out: &mut std::io::BufWriter<W>) {
    let n: usize = sc.next();
    let k: usize = sc.next();
    let mut g = vec![vec![]; n];
    let mut lca = LCA::new(n);
    for _ in 1..n {
        let a = sc.next::<usize>() - 1;
        let b = sc.next::<usize>() - 1;
        let c = sc.next::<u64>();
        lca.add_edge(a, b);
        g[a].push((b, c));
        g[b].push((a, c));
    }
    let root = n - 1;
    lca.build(root);
    let inf = std::u64::MAX / 10;
    let mut depth = vec![inf; n];
    depth[root] = 0;
    let mut dfs = vec![root];
    while let Some(v) = dfs.pop() {
        let d = depth[v];
        for &(u, c) in g[v].iter() {
            if depth[u].chmin(d + c) {
                dfs.push(u);
            }
        }
    }
    let dijkstra = |src: &[usize]| -> Vec<u64> {
        let mut dp = vec![inf; n];
        let mut h = std::collections::BinaryHeap::new();
        use std::cmp::*;
        for &v in src.iter() {
            dp[v] = 0;
            h.push(Reverse((0, v)));
        }
        while let Some(Reverse((d, v))) = h.pop() {
            if d > dp[v] {
                continue;
            }
            for &(u, w) in g[v].iter() {
                if dp[u].chmin(d + w) {
                    h.push(Reverse((dp[u], u)));
                }
            }
        }
        dp
    };
    let mut memo = vec![];
    for _ in 0..k {
        let m: usize = sc.next();
        let p: u64 = sc.next();
        let mut x = vec![0usize; m];
        for x in x.iter_mut() {
            *x = sc.next::<usize>() - 1;
        }
        memo.push((p, dijkstra(&x)));
    }
    let mut g = vec![vec![inf; 2 * k]; 2 * k];
    for (i, a) in memo.iter().enumerate() {
        g[i][i] = 0;
        g[i][i + k] = a.0;
        g[i + k][i + k] = 0;
        for (j, b) in memo.iter().enumerate().take(i) {
            let d = a.1.iter().zip(b.1.iter()).map(|p| *p.0 + *p.1).min().unwrap();
            g[i + k][j] = d;
            g[j + k][i] = d;
        }
    }
    for x in 0..(2 * k) {
        for i in 0..(2 * k) {
            for j in 0..(2 * k) {
                let d = g[i][x] + g[x][j];
                g[i][j].chmin(d);
            }
        }
    }
    let q: usize = sc.next();
    for _ in 0..q {
        let s = sc.next::<usize>() - 1;
        let t = sc.next::<usize>() - 1;
        let mut ans = depth[s] + depth[t] - 2 * depth[lca.query(s, t)];
        for (i, a) in memo.iter().enumerate() {
            ans.chmin(a.1[s] + a.0 + a.1[t]);
            for (j, b) in memo.iter().enumerate() {
                ans.chmin(a.1[s] + g[i][j + k] + b.1[t]);
            }
        }
        writeln!(out, "{}", ans).ok();
    }
}