Submission #2377086


Source Code Expand

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

const BASE: u32 = 0;

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, BASE));
        add(&mut graph, (q, BASE));
        add(&mut graph, (p, c));
        add(&mut graph, (q, c));

        if graph[&(p, c)].is_empty() {
            graph.get_mut(&(p, c)).unwrap().push((p, BASE, 0));
            graph.get_mut(&(p, BASE)).unwrap().push((p, c, 1));
        }
        if graph[&(q, c)].is_empty() {
            graph.get_mut(&(q, c)).unwrap().push((q, BASE, 0));
            graph.get_mut(&(q, BASE)).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 start = 0;
    let goal = n - 1;

    add(&mut graph, (start, BASE));
    add(&mut graph, (goal, BASE));

    let mut queue: VecDeque<(usize, u32)> = VecDeque::new();
    let mut dist = BTreeMap::new();
    dist.insert((start, BASE), 0);
    queue.push_front((start, BASE));
    while !queue.is_empty() {
        let (v, company) = queue.pop_front().unwrap();
        let v_dist = *dist.get(&(v, company)).unwrap();
        if v == goal && company == BASE {
            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 600
Code Size 4002 Byte
Status AC
Exec Time 940 ms
Memory 110844 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 600 / 600
Status AC
AC × 59
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 345 ms 37116 KB
03.txt AC 813 ms 110844 KB
04.txt AC 571 ms 90364 KB
05.txt AC 657 ms 82172 KB
06.txt AC 456 ms 65788 KB
07.txt AC 408 ms 61692 KB
08.txt AC 682 ms 102652 KB
09.txt AC 396 ms 65788 KB
10.txt AC 519 ms 71932 KB
11.txt AC 416 ms 61692 KB
12.txt AC 113 ms 20732 KB
13.txt AC 232 ms 33020 KB
14.txt AC 320 ms 55548 KB
15.txt AC 361 ms 51452 KB
16.txt AC 431 ms 59644 KB
17.txt AC 473 ms 63740 KB
18.txt AC 181 ms 26876 KB
19.txt AC 326 ms 51452 KB
20.txt AC 465 ms 67836 KB
21.txt AC 508 ms 92412 KB
22.txt AC 440 ms 67836 KB
23.txt AC 572 ms 82172 KB
24.txt AC 360 ms 61692 KB
25.txt AC 100 ms 18684 KB
26.txt AC 219 ms 33020 KB
27.txt AC 324 ms 57596 KB
28.txt AC 436 ms 69884 KB
29.txt AC 399 ms 67836 KB
30.txt AC 332 ms 59644 KB
31.txt AC 244 ms 39164 KB
32.txt AC 393 ms 57596 KB
33.txt AC 385 ms 65788 KB
34.txt AC 290 ms 43260 KB
35.txt AC 100 ms 20732 KB
36.txt AC 179 ms 28924 KB
37.txt AC 287 ms 43260 KB
38.txt AC 267 ms 41212 KB
sample_01.txt AC 2 ms 4352 KB
sample_02.txt AC 2 ms 4352 KB
sample_03.txt AC 2 ms 4352 KB
w1.txt AC 445 ms 57724 KB
w10.txt AC 655 ms 94460 KB
w11.txt AC 136 ms 18684 KB
w12.txt AC 227 ms 26876 KB
w13.txt AC 536 ms 49404 KB
w14.txt AC 754 ms 94460 KB
w15.txt AC 72 ms 21552 KB
w16.txt AC 143 ms 20732 KB
w17.txt AC 201 ms 20732 KB
w18.txt AC 402 ms 37116 KB
w2.txt AC 525 ms 61692 KB
w3.txt AC 654 ms 73980 KB
w4.txt AC 334 ms 51452 KB
w5.txt AC 688 ms 106748 KB
w6.txt AC 533 ms 82172 KB
w7.txt AC 860 ms 104700 KB
w8.txt AC 921 ms 100604 KB
w9.txt AC 940 ms 100604 KB