Submission #36835455

---

Source Code Expand

// -*- coding:utf-8-unix -*-

#![allow(unused_imports)]
#![allow(unused_macros)]
use std::io::{BufRead, BufReader, BufWriter, Write, stdin, stdout, stderr, Read};
use std::collections::*;
//use proconio::{input, marker::{Bytes, Chars, Isize1, Usize1}, source::{auto::AutoSource, line::LineSource, once::OnceSource}};
use bitset_fixed::BitSet;
use itertools::*;
use num::integer::*;
use petgraph::{algo::*, Directed, Undirected};
use petgraph::graph::{Graph, DiGraph, NodeIndex, UnGraph};
use petgraph::unionfind::UnionFind;
use petgraph::visit::{Bfs, Dfs, EdgeRef, IntoEdges, NodeCount, NodeIndexable, Visitable, VisitMap};
use rand::{distributions::WeightedIndex, rngs::ThreadRng, seq::SliceRandom, Rng};
use superslice::Ext;

/// input macros based on tanakh's input macro / proconio-rs.
/// tanakh's input macro: <https://qiita.com/tanakh/items/0ba42c7ca36cd29d0ac8>
/// proconio-rs: <https://docs.rs/proconio/0.3.8/proconio/>
/// this macro recieve `Iterator<Item = u8>` input source.
#[allow(unused)]
macro_rules! finput {
    (from $iter: expr, $($r:tt)*) => {
        finput_inner!{$iter, $($r)*}
    };
    ($($r:tt)*) => {
        let stdin = stdin();
        let mut iter = ProconIBufIter::new(stdin.lock());
        finput_inner!{iter, $($r)*}
        drop(iter);
        drop(stdin);
    };
}
#[allow(unused)]
macro_rules! finput_inner {
    ($iter: expr) => {};
    ($iter: expr, ) => {};
    ($iter: expr, mut $var:ident : $t:tt $($r:tt)*) => {
        let mut $var = fread_value!($iter, $t);
        finput_inner!{$iter $($r)*}
    };
    ($iter: expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = fread_value!($iter, $t);
        finput_inner!{$iter $($r)*}
    };
}
#[allow(unused)]
macro_rules! fread_value {
    ($iter:expr, ( $($t:tt),* )) => { ( $(fread_value!($iter, $t)),* ) };
    ($iter:expr, [ $t:tt ; $len:expr ]) => { (0..$len).map(|_| fread_value!($iter, $t)).collect::<Vec<_>>() };
    ($iter:expr, u128) => { $iter.parse_uint::<u128>().unwrap() };
    ($iter:expr, usize) => { $iter.parse_uint::<usize>().unwrap() };
    ($iter:expr, usize1) => { $iter.parse_uint::<usize>().unwrap() - 1 };
    ($iter:expr, u64) => { $iter.parse_uint::<u64>().unwrap() };
    ($iter:expr, u64_1) => { $iter.parse_uint::<u64>().unwrap() - 1 };
    ($iter:expr, u32) => { $iter.parse_uint::<u32>().unwrap() };
    ($iter:expr, u32_1) => { $iter.parse_uint::<u32>().unwrap() - 1 };
    ($iter:expr, u16) => { $iter.parse_uint::<u16>().unwrap() };
    ($iter:expr, u8) => { $iter.parse_uint::<u8>().unwrap() };
    ($iter:expr, i128) => { $iter.parse_iint::<i128>().unwrap() };
    ($iter:expr, isize) => { $iter.parse_iint::<isize>().unwrap() };
    ($iter:expr, i64) => { $iter.parse_iint::<i64>().unwrap() };
    ($iter:expr, i32) => { $iter.parse_iint::<i32>().unwrap() };
    ($iter:expr, i16) => { $iter.parse_iint::<i16>().unwrap() };
    ($iter:expr, i8) => { $iter.parse_iint::<i8>().unwrap() };
    ($iter:expr, byte) => { $iter.get_byte().unwrap() };
    ($iter:expr, Bytes) => { $iter.get_bytes().unwrap() };
    ($iter:expr, Chars) => { $iter.get_bytes().unwrap().iter().map(|&c| c as char).collect::<Vec<_>>() };
    ($iter:expr, String) => { unsafe { std::string::String::from_utf8_unchecked($iter.get_bytes().unwrap()) } };
    ($iter:expr, LineBytes) => { $iter.get_line_bytes().unwrap() };
    ($iter:expr, LineBytesTrim) => { $iter.get_line_bytes_trim().unwrap() };
    ($iter:expr, LineString) => { unsafe { std::string::String::from_utf8_unchecked($iter.get_line_bytes().unwrap()) } };
    ($iter:expr, LineStringTrim) => { unsafe { std::string::String::from_utf8_unchecked($iter.get_line_bytes_trim().unwrap()) } };
    ($iter:expr, $t:ty) => { unsafe { std::string::String::from_utf8_unchecked($iter.get_bytes()).unwrap() }.parse::<$t>().expect("Parse error") };
}

#[allow(dead_code)]
enum Algo {
    Dijkstra,
    MaxkDijkstra,
    ZeroOneBFS,
    ZeroOneBFSBitset,
    ZeroOneBFSScoreVec,
    BFS,
}
const USE_ALGO: Algo = Algo::BFS;

fn max_k_dijkstra<G, F, K>(
    graph: G,
    start: G::NodeId,
    goal: Option<G::NodeId>,
    max_k: K,
    mut edge_cost: F,
) -> HashMap<G::NodeId, K>
where
    G: IntoEdges + NodeIndexable + Visitable,
    G::NodeId: Eq + std::hash::Hash,
    K: Measure + Copy + Into<u32>,
    F: FnMut(G::EdgeRef) -> K,
{
    let mut discovered = graph.visit_map();
    let mut scores = HashMap::new();
    let mut stack = VecDeque::from(vec![vec![]; max_k.into() as usize + 1]);
    let zero_score = K::default();
    scores.insert(start, zero_score);
    stack[0].push((start, zero_score));
    while stack.iter().any(|v| !v.is_empty()) {
        while let Some((node, node_score)) = stack[0].pop() {
            if !discovered.visit(node) {
                continue;
            }
            if goal.as_ref() == Some(&node) {
                break;
            }
            for edge in graph.edges(node) {
                let next_node = edge.target();
                if discovered.is_visited(&next_node) {
                    continue;
                }
                let edge_cost_value = edge_cost(edge);
                let next_score = node_score + edge_cost_value;
                match scores.entry(next_node) {
                    hash_map::Entry::Occupied(ent) => {
                        if next_score < *ent.get() {
                            *ent.into_mut() = next_score;
                        } else {
                            continue;
                        }
                    },
                    hash_map::Entry::Vacant(ent) => {
                        ent.insert(next_score);
                    },
                }
                stack[edge_cost_value.into() as usize].push((next_node, next_score));
            }
        }
        stack.rotate_left(1);
    }
    scores
}

fn zero_one_bfs<G, F, K>(
    graph: G,
    start: G::NodeId,
    goal: Option<G::NodeId>,
    mut edge_weighted: F,
) -> HashMap<G::NodeId, K>
where
    G: IntoEdges + Visitable,
    G::NodeId: Eq + std::hash::Hash,
    F: FnMut(G::EdgeRef) -> bool,
    K: Measure + Copy + num::Zero + num::One,
{
    let mut discovered = graph.visit_map();
    let mut scores = HashMap::new();
    let mut stack = VecDeque::new();
    let zero_score = K::zero();
    let one_score = K::one();
    scores.insert(start, zero_score);
    stack.push_front((start, zero_score));
    while let Some((node, node_score)) = stack.pop_front() {
        if !discovered.visit(node) {
            continue;
        }
        if goal.as_ref() == Some(&node) {
            break;
        }
        for edge in graph.edges(node) {
            let next_node = edge.target();
            if discovered.is_visited(&next_node) {
                continue;
            }
            let edge_weighted_bool = edge_weighted(edge);
            let edge_cost_value = match edge_weighted_bool {
                false => zero_score,
                true => one_score,
            };
            let next_score = node_score + edge_cost_value;
            match scores.entry(next_node) {
                hash_map::Entry::Occupied(ent) => {
                    if next_score < *ent.get() {
                        *ent.into_mut() = next_score;
                    } else {
                        continue;
                    }
                },
                hash_map::Entry::Vacant(ent) => {
                    ent.insert(next_score);
                },
            }
            match edge_weighted_bool {
                false => stack.push_front((next_node, next_score)),
                true => stack.push_back((next_node, next_score)),
            }
        }
    }
    scores
}

fn zero_one_bfs_bitset<G, F, K>(
    graph: G,
    start: G::NodeId,
    goal: G::NodeId,
    mut edge_weighted: F,
) -> Option<K>
where
    G: IntoEdges + Visitable,
    G::NodeId: Eq + std::hash::Hash,
    F: FnMut(G::EdgeRef) -> bool,
    K: Measure + Copy + num::Zero + num::One,
{
    let mut discovered_map = graph.visit_map();
    let mut stacked_map = graph.visit_map();
    let mut stack = VecDeque::new();
    let zero_score = K::zero();
    let one_score = K::one();
    stack.push_front((start, zero_score));
    while let Some((node, node_score)) = stack.pop_front() {
        if !discovered_map.visit(node) {
            continue;
        }
        if goal == node {
            return Some(node_score);
        }
        for edge in graph.edges(node) {
            let next_node = edge.target();
            if discovered_map.is_visited(&next_node) {
                continue;
            }
            let edge_weighted_bool = edge_weighted(edge);
            let edge_cost_value = match edge_weighted_bool {
                false => zero_score,
                true => one_score,
            };
            let next_score = node_score + edge_cost_value;
            // 重さ0の辺が多すぎるグラフだとstackが爆発するかも
            if stacked_map.visit(next_node) || !edge_weighted_bool {
                match edge_weighted_bool {
                    false => stack.push_front((next_node, next_score)),
                    true => stack.push_back((next_node, next_score)),
                }
            }
        }
    }
    None
}

fn zero_one_bfs_vec<G, F, K>(
    graph: G,
    start: G::NodeId,
    goal: G::NodeId,
    mut edge_cost: F,
) -> Option<K>
where
    G: IntoEdges + NodeCount + NodeIndexable + Visitable,
    G::NodeId: Eq + std::hash::Hash,
    F: FnMut(G::EdgeRef) -> bool,
    K: Measure + Copy + Eq + num::Zero + num::One,
{
    let mut discovered_map = graph.visit_map();
    let mut score_vec = vec![None; graph.node_bound()];
    let mut stack = VecDeque::new();
    let mut result = None;
    let zero_score = K::default();
    let one_score = K::one();
    score_vec[graph.to_index(start)] = Some(zero_score);
    stack.push_front((start, zero_score));
    while let Some((node, node_score)) = stack.pop_front() {
        if !discovered_map.visit(node) {
            continue;
        }
        if goal == node {
            result = Some(node_score);
            break;
        }
        for edge in graph.edges(node) {
            let next_node = edge.target();
            if discovered_map.is_visited(&next_node) {
                continue;
            }
            let edge_cost_bool = edge_cost(edge);
            let edge_cost_value = if edge_cost_bool { one_score } else { zero_score };
            let next_score = node_score + edge_cost_value;
            if let Some(prev_next_score) = score_vec[graph.to_index(next_node)] {
                if prev_next_score <= next_score {
                    continue;
                }
            }
            score_vec[graph.to_index(next_node)] = Some(next_score);
            if edge_cost_bool {
                stack.push_back((next_node, next_score));
            } else {
                stack.push_front((next_node, next_score));
            }
        }
    }
    result
}

fn bfs<G, K>(
    graph: G,
    start: G::NodeId,
    goal: G::NodeId,
) -> Option<K>
where
    G: IntoEdges + NodeCount + NodeIndexable + Visitable,
    G::NodeId: Eq + std::hash::Hash,
    K: Measure + Copy + num::Zero + num::One,
{
    let mut stacked_map = graph.visit_map();
    let mut stack = VecDeque::with_capacity(graph.node_count());
    let zero_score = K::zero();
    let one_score = K::one();
    stack.push_front((start, zero_score));
    stacked_map.visit(start);
    while let Some((node, node_score)) = stack.pop_front() {
        if goal == node {
            return Some(node_score);
        }
        let next_score = node_score + one_score;
        for edge in graph.edges(node) {
            let next_node = edge.target();
            if stacked_map.visit(next_node) {
                stack.push_back((next_node, next_score));
            }
        }
    }
    None
}

fn main() {
    let _tins = std::time::Instant::now();
    //let out = stdout();
    //let mut out = BufWriter::new(out.lock());
    //let err = stderr();
    //let mut err = BufWriter::new(err.lock());
    //let sin = stdin();
    //let mut source = LineSource::new(BufReader::new(sin.lock()));
    /*
    input! {
        //from &mut source,
        n: usize, m: usize, k: usize,
        uva: [(Usize1, Usize1, usize); m],
        s: [Usize1; k],
    }
    */
    /*
    let ibuf = getibuf();
    let mut iter = ibuf.iter().cloned();
    let (n, m, k): (usize, usize, usize) = (iter.parse_uint(), iter.parse_uint(), iter.parse_uint());
    let uva: Vec<_> = (0..m).map(|_| (iter.parse_uint::<usize>()-1, iter.parse_uint::<usize>()-1, iter.parse_uint::<usize>())).collect();
    let s: Vec<_> = (0..k).map(|_| iter.parse_uint::<usize>()-1).collect();
    */

    //let stdin = std::io::stdin();
    //let mut source = ProconIBufIter::new(stdin.lock());
    finput!{
        //from source,
        n: usize, m: usize, k: usize,
        uva: [(u32_1, u32_1, u32); m],
        s: [u32_1; k],
    };

    let _input_dur = _tins.elapsed();

    let n1 = n - 1;
    let mut graph = UnGraph::<(), ()>::with_capacity(n * 2 - k, m);
    let mut switch_bitset = BitSet::new(n);
    for si in s.iter().cloned() {
        switch_bitset.set(si as usize, true);
    }
    switch_bitset.set(n1, true); // goal_shortcut
    let mut nodes = Vec::with_capacity(n * 2);
    for i in 0..n {
        // switchの存在するノードは片側に座標圧縮
        if switch_bitset[i as usize] {
            // node both a = 0, 1
            let sw_node = graph.add_node(());
            nodes.push(sw_node);
            nodes.push(sw_node);
        } else {
            nodes.push(graph.add_node(())); // node side a = 0
            nodes.push(graph.add_node(())); // node side a = 1
        }
    }
    let start_node = nodes[1];
    let goal_node = nodes[n1 * 2];
    for (u, v, a) in uva.iter().cloned() {
        let _passage = graph.add_edge(
            nodes[u as usize * 2 + a as usize],
            nodes[v as usize * 2 + a as usize],
            ()
        );
    }

    let result: Option<u32> = match USE_ALGO {
        Algo::Dijkstra => dijkstra(
            // ダイクストラ法
            &graph,
            start_node,
            Some(goal_node),
            |_e| 1 // *_e.weight()
        ).get(&goal_node).cloned(),
        Algo::MaxkDijkstra => max_k_dijkstra(
            // 重み制限有りのダイクストラ法
            &graph,
            start_node,
            Some(goal_node),
            1,
            |_e| 1 // *_e.weight()
        ).get(&goal_node).cloned(),
        Algo::ZeroOneBFS => zero_one_bfs(
            // 01-BFS hashmap
            &graph,
            start_node,
            Some(goal_node),
            |_e| true // *_e.weight() != 0
        ).get(&goal_node).cloned(),
        Algo::ZeroOneBFSBitset => zero_one_bfs_bitset(
            // 01-BFS bitset
            &graph,
            start_node,
            goal_node,
            |_e| true // *_e.weight() != 0
        ),
        Algo::ZeroOneBFSScoreVec => zero_one_bfs_vec(
            // 01-BFS vector
            &graph,
            start_node,
            goal_node,
            |_e| true // *_e.weight() != 0
        ),
        Algo::BFS => bfs(
            // BFS
            &graph,
            start_node,
            goal_node,
        ),
    };

    let _solve_dur = _tins.elapsed();

    match result {
        Some(r) => println!("{}", r),
        None => println!("{}", -1),
    }

    let _output_dur = _tins.elapsed();

    eprintln!(
        "{} {} {}",
        _input_dur.as_micros(),
        _solve_dur.as_micros(),
        _output_dur.as_micros(),
    );

    //writeln!(&mut out, "{}", count).unwrap();
    //writeln!(&mut err, "{}", count).unwrap();
    //out.flush().unwrap();
    //err.flush().unwrap();
}

/// chmax, chmin sugar syntax
trait Change { fn chmax(&mut self, x: Self); fn chmin(&mut self, x: Self); }
impl<T: PartialOrd> Change for T {
    fn chmax(&mut self, x: T) { if *self < x { *self = x; }}
    fn chmin(&mut self, x: T) { if *self > x { *self = x; }}
}
#[allow(unused)]
/// Allocate buffer space, Save interruption pointer
struct ProconIBuf {
    raw: *mut u8,
    len: usize,
    ptr: *mut u8,
    end: *mut u8,
}
/// Interaction with `std::io::Read` Trait, Implementation of `Iterator<Item = u8>`
struct ProconIBufIter<R: std::io::BufRead> {
    inner: R,
    raw: *const u8,
    len: usize,
    ptr: *const u8,
    end: *const u8,
}
/// Allocate buffer once per thread (Currently does not support multi-threading)
trait ProconReader<R> {
    /// set new reader
    fn new(inner: R) -> Self;
}
impl<R: std::io::BufRead> ProconReader<R> for ProconIBufIter<R> {
    fn new(inner: R) -> Self {
        let mut bufiter = Self { inner, raw: std::ptr::null(), len: 0, ptr: std::ptr::null(), end: std::ptr::null() };
        unsafe { bufiter.inner_read() };
        bufiter
    }
}
impl<R: std::io::BufRead> ProconIBufIter<R> {
    /// check end of buffer
    fn is_empty(&self) -> bool {
        self.ptr == self.end
    }
    /// get now pointer & increment pointer
    unsafe fn next_unchecked(&mut self) -> u8 {
        let p = self.ptr;
        self.ptr = p.add(1);
        *p
    }
    /// read buffer
    unsafe fn inner_read(&mut self) -> bool {
        assert!(self.is_empty());
        self.inner.consume(self.ptr as usize - self.raw as usize);
        let buffer = self.inner.fill_buf().unwrap();
        let raw = buffer.as_ptr();
        let len = buffer.len();
        self.raw = raw;
        self.len = len;
        self.ptr = raw;
        self.end = raw.add(len);
        self.len > 0
    }
}
impl<R: std::io::BufRead> Iterator for ProconIBufIter<R> {
    type Item = u8;
    /// fetch next byte
    fn next(&mut self) -> Option<Self::Item> {
        if !self.is_empty() {
            unsafe { Some(self.next_unchecked()) }
        } else {
            match unsafe { self.inner_read() } {
                true => unsafe { Some(self.next_unchecked()) },
                false => None,
            }
        }
    }
}
impl<R: std::io::BufRead> Drop for ProconIBufIter<R> {
    /// Saving the pointer on interruption
    fn drop(&mut self) {
        self.inner.consume(self.ptr as usize - self.raw as usize);
    }
}
#[allow(unused)]
/// get all stdio input (for performance comparison with whole batch loading)
/// ```
/// let ibuf = getibuf();
/// let mut iter = ibuf.iter().cloned();
/// finput!{ from iter, n: usize, a: [u32; n] }
/// ```
fn getibuf() -> Vec<u8> {
    let mut ibuf = vec![];
    std::io::Read::read_to_end(&mut std::io::stdin().lock(), &mut ibuf).unwrap();
    ibuf
}
trait PrimInt: Copy + std::cmp::Ord + std::ops::BitAnd<Output = Self> + std::ops::Add<Output = Self> + std::ops::Sub<Output = Self> + std::ops::Mul<Output = Self> {
    fn wrapping_sub(self, o: Self) -> Self;
}
macro_rules! impl_prim_int(($($ty:ty),*) => {$(impl PrimInt for $ty {
    fn wrapping_sub(self, o: Self) -> Self { self.wrapping_sub(o) }
})*});
impl_prim_int!(u8,u16,u32,u64,u128,usize,i8,i16,i32,i64,i128,isize);
/// speed frenzy input parser for program compete (fail parse may cause panic)
trait ProconParse {
    /// parse unsigned integer
    fn parse_uint<U: PrimInt + std::convert::From<u8>>(&mut self) -> Option<U>;
    /// parse signed integer
    fn parse_iint<I: PrimInt + std::convert::From<u8> + std::ops::Neg<Output = I>>(&mut self) -> Option<I>;
    /// get char (printable char)
    fn get_byte(&mut self) -> Option<u8>;
    /// get chars (printable word)
    fn get_bytes(&mut self) -> Option<Vec<u8>>;
    /// get line chars (sp+printable ascii)
    fn get_line_bytes(&mut self) -> Option<Vec<u8>>;
    /// get line chars (trimed sp+printable ascii)
    fn get_line_bytes_trim(&mut self) -> Option<Vec<u8>>;
}
impl<T: Iterator<Item = u8>> ProconParse for T {
    fn parse_uint<U: PrimInt + std::convert::From<u8>>(&mut self) -> Option<U> { loop { match self.next() {
        Some(c) => {
            let mut x = U::from(c).wrapping_sub(U::from(0x30));
            if x.gt(&U::from(9)) { continue; }
            while let Some(c) = self.next() {
                let c = U::from(c).wrapping_sub(U::from(0x30));
                if c.gt(&U::from(9)) { break; }
                x = x.mul(U::from(10)).add(c);
            }
            break Some(x);
        },
        None => break None,
    }}}
    fn parse_iint<I: PrimInt + std::ops::Neg<Output = I> + std::convert::From<u8>>(&mut self) -> Option<I> { loop { match self.next() {
        Some(b'-') => {
            let mut x = if let Some(c) = self.next() {
                let c = I::from(c).wrapping_sub(I::from(0x30));
                if c.le(&I::from(9)) { c.neg() } else { break None; }
            } else { break None; };
            while let Some(c) = self.next() {
                let c = I::from(c).wrapping_sub(I::from(0x30));
                if c.gt(&I::from(9)) { break; }
                x = x.mul(I::from(10)).sub(c);
            }
            break Some(x);
        }
        Some(c) => {
            let mut x = I::from(c).wrapping_sub(I::from(0x30));
            if !(I::from(0)..=I::from(9)).contains(&x) { continue; }
            while let Some(c) = self.next() {
                let c = I::from(c).wrapping_sub(I::from(0x30));
                if !(I::from(0)..=I::from(9)).contains(&c) { break; }
                x = x.mul(I::from(10)).add(c);
            }
            break Some(x);
        }
        None => break None,
    }}}
    fn get_byte(&mut self) -> Option<u8> { loop { match self.next() {
        Some(c @ b'!'..=b'~') => break Some(c),
        Some(_) => continue,
        None => break None,
    }}}
    fn get_bytes(&mut self) -> Option<Vec<u8>> { loop { match self.next() {
        Some(c @ b'!'..=b'~') => {
            let mut v = vec![c];
            while let Some(c @ b'!'..=b'~') = self.next() { v.push(c); }
            break Some(v);
        },
        Some(_) => continue,
        None => break None,
    }}}
    fn get_line_bytes(&mut self) -> Option<Vec<u8>> { loop { match self.next() {
        Some(c @ b' '..=b'~') => {
            let mut v = vec![c];
            while let Some(c @ b' '..=b'~') = self.next() { v.push(c); }
            break Some(v);
        },
        Some(_) => continue,
        None => break None,
    }}}
    fn get_line_bytes_trim(&mut self) -> Option<Vec<u8>> { loop { match self.next() {
        Some(c @ b'!'..=b'~') => {
            let mut v = vec![c];
            while let Some(c @ b' '..=b'~') = self.next() { v.push(c); }
            while v.last() == Some(&b' ') { v.pop(); }
            break Some(v);
        },
        Some(_) => continue,
        None => break None,
    }}}
}

Submission Info

Judge Result