Submission #2377076


Source Code Expand

use std::collections::BTreeMap;
use std::collections::VecDeque;

fn main() {
    let mut sc = Scanner::new();
    let n: usize = sc.read();
    let m: usize = sc.read();

    let mut graph: BTreeMap<(usize, u32), Vec<(usize, u32, usize)>> = BTreeMap::new();
    for _ in 0..m {
        let p = sc.read::<usize>() - 1;
        let q = sc.read::<usize>() - 1;
        let c: u32 = sc.read();

        add(&mut graph, (p, 0));
        add(&mut graph, (q, 0));
        add(&mut graph, (p, c));
        add(&mut graph, (q, c));

        if graph[&(p, c)].is_empty() {
            graph.get_mut(&(p, c)).unwrap().push((p, 0, 0));
            graph.get_mut(&(p, 0)).unwrap().push((p, c, 1));
        }
        if graph[&(q, c)].is_empty() {
            graph.get_mut(&(q, c)).unwrap().push((q, 0, 0));
            graph.get_mut(&(q, 0)).unwrap().push((q, c, 1));
        }

        graph.get_mut(&(p, c)).unwrap().push((q, c, 0));
        graph.get_mut(&(q, c)).unwrap().push((p, c, 0));
    }

    let mut queue: VecDeque<(usize, u32)> = VecDeque::new();
    let mut dist = BTreeMap::new();
    dist.insert((0, 0), 0);
    queue.push_front((0, 0));
    while !queue.is_empty() {
        let (v, company) = queue.pop_front().unwrap();
        let v_dist = *dist.get(&(v, company)).unwrap();
        if v == n - 1 && company == 0 {
            println!("{}", v_dist);
            return;
        }

        for &(to, next_company, edge_cost) in &graph[&(v, company)] {
            let to_dist = *dist.get(&(to, next_company)).unwrap_or(&std::usize::MAX);
            if v_dist + edge_cost >= to_dist {
                continue;
            }
            dist.insert((to, next_company), v_dist + edge_cost);
            if edge_cost == 0 {
                queue.push_front((to, next_company));
            } else {
                queue.push_back((to, next_company));
            }
        }
    }

    println!("-1");
}

fn add<K, T>(map: &mut BTreeMap<K, Vec<T>>, key: K)
where
    K: std::cmp::Ord,
{
    if !map.contains_key(&key) {
        map.insert(key, Vec::new());
    }
}

struct Scanner {
    ptr: usize,
    length: usize,
    buf: Vec<u8>,
    small_cache: Vec<u8>,
}

impl Scanner {
    fn new() -> Scanner {
        Scanner {
            ptr: 0,
            length: 0,
            buf: vec![0; 1024],
            small_cache: vec![0; 1024],
        }
    }

    fn load(&mut self) {
        use std::io::Read;
        let mut s = std::io::stdin();
        self.length = s.read(&mut self.buf).unwrap();
    }

    fn byte(&mut self) -> u8 {
        if self.ptr >= self.length {
            self.ptr = 0;
            self.load();
            if self.length == 0 {
                self.buf[0] = b'\n';
                self.length = 1;
            }
        }

        self.ptr += 1;
        return self.buf[self.ptr - 1];
    }

    fn is_space(b: u8) -> bool {
        b == b'\n' || b == b'\r' || b == b'\t' || b == b' '
    }

    fn read<T>(&mut self) -> T
    where
        T: std::str::FromStr,
        T::Err: std::fmt::Debug,
    {
        let mut b = self.byte();
        while Scanner::is_space(b) {
            b = self.byte();
        }

        for pos in 0..self.small_cache.len() {
            self.small_cache[pos] = b;
            b = self.byte();
            if Scanner::is_space(b) {
                return String::from_utf8_lossy(&self.small_cache[0..(pos + 1)])
                    .parse()
                    .unwrap();
            }
        }

        let mut v = self.small_cache.clone();
        while !Scanner::is_space(b) {
            v.push(b);
            b = self.byte();
        }
        return String::from_utf8_lossy(&v).parse().unwrap();
    }
}

Submission Info

Submission Time
Task E - Snuke's Subway Trip
User kenkoooo
Language Rust (1.15.1)
Score 0
Code Size 3824 Byte
Status RE
Exec Time 939 ms
Memory 110844 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 600
Status AC
AC × 57
RE × 2
Set Name Test Cases
Sample
All 01.txt, 02.txt, 03.txt, 04.txt, 05.txt, 06.txt, 07.txt, 08.txt, 09.txt, 10.txt, 11.txt, 12.txt, 13.txt, 14.txt, 15.txt, 16.txt, 17.txt, 18.txt, 19.txt, 20.txt, 21.txt, 22.txt, 23.txt, 24.txt, 25.txt, 26.txt, 27.txt, 28.txt, 29.txt, 30.txt, 31.txt, 32.txt, 33.txt, 34.txt, 35.txt, 36.txt, 37.txt, 38.txt, sample_01.txt, sample_02.txt, sample_03.txt, w1.txt, w10.txt, w11.txt, w12.txt, w13.txt, w14.txt, w15.txt, w16.txt, w17.txt, w18.txt, w2.txt, w3.txt, w4.txt, w5.txt, w6.txt, w7.txt, w8.txt, w9.txt
Case Name Status Exec Time Memory
01.txt AC 2 ms 4352 KB
02.txt AC 340 ms 37116 KB
03.txt AC 804 ms 110844 KB
04.txt RE 582 ms 90364 KB
05.txt AC 649 ms 82172 KB
06.txt AC 457 ms 65788 KB
07.txt AC 405 ms 61692 KB
08.txt AC 678 ms 102652 KB
09.txt AC 398 ms 65788 KB
10.txt AC 539 ms 71932 KB
11.txt AC 421 ms 61692 KB
12.txt AC 107 ms 20732 KB
13.txt AC 217 ms 33020 KB
14.txt AC 320 ms 55548 KB
15.txt AC 362 ms 51452 KB
16.txt AC 436 ms 59644 KB
17.txt AC 478 ms 63740 KB
18.txt AC 171 ms 26876 KB
19.txt AC 313 ms 51452 KB
20.txt AC 468 ms 67836 KB
21.txt AC 503 ms 92412 KB
22.txt AC 443 ms 67836 KB
23.txt AC 575 ms 82172 KB
24.txt AC 362 ms 61692 KB
25.txt AC 99 ms 18684 KB
26.txt AC 218 ms 33020 KB
27.txt AC 318 ms 57596 KB
28.txt AC 439 ms 69884 KB
29.txt AC 394 ms 67836 KB
30.txt AC 329 ms 59644 KB
31.txt AC 253 ms 39164 KB
32.txt AC 412 ms 57596 KB
33.txt AC 383 ms 65788 KB
34.txt AC 287 ms 43260 KB
35.txt AC 99 ms 20732 KB
36.txt AC 178 ms 28924 KB
37.txt AC 284 ms 43260 KB
38.txt AC 266 ms 41212 KB
sample_01.txt AC 2 ms 4352 KB
sample_02.txt AC 2 ms 4352 KB
sample_03.txt RE 2 ms 4352 KB
w1.txt AC 445 ms 57596 KB
w10.txt AC 649 ms 94460 KB
w11.txt AC 136 ms 18684 KB
w12.txt AC 224 ms 26876 KB
w13.txt AC 529 ms 49404 KB
w14.txt AC 749 ms 94460 KB
w15.txt AC 75 ms 21552 KB
w16.txt AC 143 ms 20732 KB
w17.txt AC 198 ms 20732 KB
w18.txt AC 398 ms 37116 KB
w2.txt AC 509 ms 61692 KB
w3.txt AC 629 ms 73980 KB
w4.txt AC 320 ms 51452 KB
w5.txt AC 697 ms 106748 KB
w6.txt AC 536 ms 82172 KB
w7.txt AC 865 ms 104700 KB
w8.txt AC 922 ms 100604 KB
w9.txt AC 939 ms 100604 KB