AtCoder Beginner Contest 408 E

https://atcoder.jp/contests/abc408/tasks/abc408_e

ラベルを2進で考えて、上のビットから1が必要かどうか調べます。すなわち1になっていない辺だけで1とNが繋がっているか調べます。
例えば、入力例1は、下から3番目のビットが1でない辺、すなわち4の辺を抜くと、1⇒2⇒3⇒4と辿れます。3番目のビットが0で2番目の1の辺を除くと、すなわちラベルが2と3の辺をさらに抜くと辿れません。なので2番目のビットはどちらでも同じです。抜いた辺は元に戻します。1番目のビットが1の辺を除くと、すなわちラベルが1と3の辺を除いても同じです。なので、3が最小値です。

// Minimum OR Path
#![allow(non_snake_case)]


//////////////////// library ////////////////////

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

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


//////////////////// UnionFind ////////////////////

use std::cmp::max;
type Node = usize;

struct UnionFind {
    parents: Vec<Node>,
    heights: Vec<i32>,
}

impl UnionFind {
    fn new(N: usize) -> UnionFind {
        let parents: Vec<Node> = (0..N).collect();
        let heights: Vec<i32> = vec![1; N];
        UnionFind { parents, heights }
    }
    
    fn is_root(&self, v: Node) -> bool {
        self.parents[v] == v
    }
    
    fn is_connected(&self, u: Node, v: Node) -> bool {
        self.root(u) == self.root(v)
    }
    
    fn connect(&mut self, u: Node, v: Node) {
        let r1 = self.root(u);
        let r2 = self.root(v);
        if r1 == r2 {
            return
        }
        
        let h1 = self.heights[r1];
        let h2 = self.heights[r2];
        if h1 <= h2 {   // r2にr1がぶら下がる
            self.parents[r1] = r2;
            self.heights[r2] = max(self.heights[r2], self.heights[r1]+1);
        }
        else {
            self.parents[r2] = r1;
            self.heights[r1] = max(self.heights[r1], self.heights[r2]+1);
        }
    }
    
    fn root(&self, v0: Node) -> Node {
        if self.is_root(v0) {
            v0
        }
        else {
            let p = self.parents[v0];
            self.root(p)
        }
    }
}


//////////////////// process ////////////////////

type Weight = i64;
type Edge = (Node, Node, Weight);

fn read_edge() -> Edge {
    let a: Vec<usize> = read_vec();
    let (u, v, w) = (a[0]-1, a[1]-1, a[2] as Weight);
    (u, v, w)
}

fn read_input() -> (usize, Vec<Edge>) {
    let v: Vec<usize> = read_vec();
    let (N, M) = (v[0], v[1]);
    let edges: Vec<Edge> = (0..M).map(|_| read_edge()).collect();
    (N, edges)
}

fn find_max_bit(edges: &Vec<Edge>) -> u32 {
    let max_w = edges.iter().map(|&(_, _, w)| w).max().unwrap();
    for i in 0u32.. {
        if (1 << i) > max_w {
            return i
        }
    }
    0
}

fn F(N: usize, mut edges: Vec<Edge>) -> Weight {
    let max_b = find_max_bit(&edges);
    let mut flag: Weight = 0;
    for i in (0..max_b).rev() {
        flag |= 1 << i;
        let mut uf = UnionFind::new(N);
        for &(u, v, w) in edges.iter() {
            if (w & flag) == 0 {
                uf.connect(u, v)
            }
        }
        if uf.is_connected(0, N-1) {
            edges = edges.into_iter().
                    filter(|&(_, _, w)| (w & flag == 0)).collect()
        }
        else {
            flag ^= 1 << i
        }
    }
    flag ^ ((1 << max_b) - 1)
}

fn main() {
    let (N, edges) = read_input();
    println!("{}", F(N, edges))
}