Submission #66763107

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;
fn main() {
    input! {
        n: usize,
        m: usize,
    }
    let mut graph: Vec<Vec<(usize, usize)>> = vec![Vec::new(); n + 1];
    for _ in 0..m {
        input! {
            a: usize,
            b: usize,
            w: usize,
        }
        graph[a].push((b, w));
    }
    // 1..vのXORの値
    let mut dist: Vec<Option<usize>> = vec![None; n + 1];
    dist[1] = Some(0);
    let mut basis_vals: Vec<usize> = Vec::new();
    let mut stack: Vec<usize> = vec![1];
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

use proconio::input;

fn main() {
    input! {
        n: usize,
        m: usize,
    }
    let mut graph: Vec<Vec<(usize, usize)>> = vec![Vec::new(); n + 1];
    for _ in 0..m {
        input! {
            a: usize,
            b: usize,
            w: usize,
        }
        graph[a].push((b, w));
    }
    // 1..vのXORの値
    let mut dist: Vec<Option<usize>> = vec![None; n + 1];
    dist[1] = Some(0);
    let mut basis_vals: Vec<usize> = Vec::new();
    let mut stack: Vec<usize> = vec![1];
    // DFSでXORの値を計算
    while let Some(u) = stack.pop() {
        let du = dist[u].unwrap();
        for &(v, w) in &graph[u] {
            match dist[v] {
                // 未訪問
                None => {
                    dist[v] = Some(du ^ w);
                    stack.push(v);
                }
                // 訪問済みならサイクルになっている
                Some(dv) => {
                    let cycle_xor = du ^ w ^ dv;
                    if cycle_xor != 0 {
                        basis_vals.push(cycle_xor);
                    }
                }
            }
        }
    }
    // 1->nへの道がないなら-1
    if dist[n].is_none() {
        println!("{}", -1);
        return;
    }
    // 上の桁から見ていって、XORを最小化する
    let mut basis: [usize; 10] = [0; 10];
    for &x in &basis_vals {
        let mut y = x;
        for b in (0..10).rev() {
            if (y & (1 << b)) != 0 {
                if basis[b] == 0 {
                    basis[b] = y;
                    break;
                } else {
                    y ^= basis[b];
                }
            }
        }
    }
    // 1->nのXORの値を求める
    let mut result = dist[n].unwrap();
    for b in (0..10).rev() {
        // 小さくなったら更新
        if basis[b] != 0 && (result ^ basis[b]) < result {
            result ^= basis[b];
        }
    }
    println!("{}", result);
}

Submission Info

Judge Result