Submission #2377087
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 |
942 ms |
Memory |
110844 KB |
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
600 / 600 |
Status |
AC
|
|
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 |
341 ms |
37116 KB |
03.txt |
AC |
824 ms |
110844 KB |
04.txt |
AC |
576 ms |
90364 KB |
05.txt |
AC |
672 ms |
82172 KB |
06.txt |
AC |
470 ms |
65788 KB |
07.txt |
AC |
410 ms |
61692 KB |
08.txt |
AC |
686 ms |
102652 KB |
09.txt |
AC |
396 ms |
65788 KB |
10.txt |
AC |
513 ms |
71932 KB |
11.txt |
AC |
409 ms |
61692 KB |
12.txt |
AC |
108 ms |
20732 KB |
13.txt |
AC |
219 ms |
33020 KB |
14.txt |
AC |
322 ms |
55548 KB |
15.txt |
AC |
369 ms |
51452 KB |
16.txt |
AC |
438 ms |
59644 KB |
17.txt |
AC |
467 ms |
63740 KB |
18.txt |
AC |
176 ms |
26876 KB |
19.txt |
AC |
313 ms |
51452 KB |
20.txt |
AC |
473 ms |
67836 KB |
21.txt |
AC |
506 ms |
92412 KB |
22.txt |
AC |
449 ms |
67836 KB |
23.txt |
AC |
578 ms |
82172 KB |
24.txt |
AC |
349 ms |
61692 KB |
25.txt |
AC |
100 ms |
18684 KB |
26.txt |
AC |
217 ms |
33020 KB |
27.txt |
AC |
327 ms |
57596 KB |
28.txt |
AC |
442 ms |
69884 KB |
29.txt |
AC |
397 ms |
67836 KB |
30.txt |
AC |
330 ms |
59644 KB |
31.txt |
AC |
249 ms |
39164 KB |
32.txt |
AC |
407 ms |
57596 KB |
33.txt |
AC |
384 ms |
65788 KB |
34.txt |
AC |
297 ms |
43260 KB |
35.txt |
AC |
103 ms |
20732 KB |
36.txt |
AC |
184 ms |
28924 KB |
37.txt |
AC |
295 ms |
43260 KB |
38.txt |
AC |
272 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 |
452 ms |
57724 KB |
w10.txt |
AC |
662 ms |
94460 KB |
w11.txt |
AC |
139 ms |
18684 KB |
w12.txt |
AC |
228 ms |
26876 KB |
w13.txt |
AC |
537 ms |
49404 KB |
w14.txt |
AC |
749 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 |
513 ms |
61692 KB |
w3.txt |
AC |
641 ms |
73980 KB |
w4.txt |
AC |
328 ms |
51452 KB |
w5.txt |
AC |
685 ms |
106748 KB |
w6.txt |
AC |
532 ms |
82172 KB |
w7.txt |
AC |
855 ms |
104700 KB |
w8.txt |
AC |
921 ms |
100604 KB |
w9.txt |
AC |
942 ms |
100604 KB |