Submission #66753087

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
use proconio::{input, marker::Usize1};
fn main() {
    input! {
        n: usize,
        m: usize,
        abw: [(Usize1, Usize1, u32); m],
    }
    let mut g = vec![vec![]; n];
    for (a, b, w) in abw {
        g[a].push((b, w));
        g[b].push((a, w));
    }
    let mut dfs = vec![0];
    let mut dist = vec![!0; n];
    dist[0] = 0;
    while let Some(u) = dfs.pop() {
        for &(v, w) in &g[u] {
            if dist[v] == !0 {
                dist[v] = dist[u] ^ w;
                dfs.push(v);
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

use proconio::{input, marker::Usize1};

fn main() {
    input! {
        n: usize,
        m: usize,
        abw: [(Usize1, Usize1, u32); m],
    }
    let mut g = vec![vec![]; n];
    for (a, b, w) in abw {
        g[a].push((b, w));
        g[b].push((a, w));
    }
    let mut dfs = vec![0];
    let mut dist = vec![!0; n];
    dist[0] = 0;
    while let Some(u) = dfs.pop() {
        for &(v, w) in &g[u] {
            if dist[v] == !0 {
                dist[v] = dist[u] ^ w;
                dfs.push(v);
            }
        }
    }
    if dist[n - 1] == !0 {
        println!("-1");
        return;
    }
    let path = dist[n - 1];
    let mut cycle = vec![];
    let mut seen = vec![false; n];
    for u in 0..n {
        if seen[u] || dist[u] == !0 {
            continue;
        }
        let mut dfs = vec![u];
        seen[u] = true;
        while let Some(u) = dfs.pop() {
            for &(v, w) in &g[u] {
                if seen[v] {
                    if dist[u] != !0 && dist[v] != !0 && dist[u] ^ dist[v] ^ w != 0 {
                        cycle.push(dist[u] ^ dist[v] ^ w);
                    }
                    continue;
                }
                dfs.push(v);
                seen[v] = true;
            }
        }
    }
    let mut basis = vec![];
    for cycle in cycle {
        let mut tmp = cycle;
        for &b in &basis {
            tmp = tmp.min(tmp ^ b);
        }
        if tmp != 0 {
            basis.push(tmp);
        }
    }
    let mut ans = path;
    for i in 0..1 << basis.len() {
        let mut tmp = path;
        for (j, &b) in basis.iter().enumerate() {
            if i >> j & 1 == 1 {
                tmp ^= b;
            }
        }
        ans = ans.min(tmp);
    }
    println!("{}", ans);
}

Submission Info

Judge Result