AtCoder Beginner Contest 396 D

https://atcoder.jp/contests/abc396/tasks/abc396_d

ノード数は10以下なので、すべてのパスについて調べるだけですね。

// Minimum XOR 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()
}


//////////////////// Graph ////////////////////

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

struct Graph {
    g: Vec<Vec<(Node, Weight)>>
}

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

impl Graph {
    fn create(N: usize, edges: Vec<Edge>) -> Graph {
        let mut g: Vec<Vec<(Node, Weight)>> = vec![vec![]; N];
        for (u, v, w) in edges {
            g[u].push((v, w));
            g[v].push((u, w))
        }
        Graph { g }
    }
}


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

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)
}

use std::cmp::min;

fn find_min_xor(u: Node, val: Weight, visited: usize, graph: &Graph) -> Weight {
    let N = graph.g.len();
    if u == N - 1 {
        val
    }
    else {
        let mut min_val = Weight::MAX;
        for &(v, w) in graph.g[u].iter() {
            if ((visited >> v) & 1) != 1 {
                let new_visited = visited | (1 << v);
                let new_val = val ^ w;
                min_val = min(min_val, find_min_xor(v, new_val,
                                                    new_visited, graph))
            }
        }
        min_val
    }
}

fn F(N: usize, edges: Vec<Edge>) -> Weight {
    let graph = Graph::create(N, edges);
    find_min_xor(0, 0, 1, &graph)
}

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