結果
問題 | No.2565 はじめてのおつかい |
ユーザー |
|
提出日時 | 2023-12-02 16:25:15 |
言語 | Rust (1.83.0 + proconio) |
結果 |
AC
|
実行時間 | 73 ms / 2,000 ms |
コード長 | 2,433 bytes |
コンパイル時間 | 14,314 ms |
コンパイル使用メモリ | 376,852 KB |
実行使用メモリ | 13,916 KB |
最終ジャッジ日時 | 2024-09-26 20:16:56 |
合計ジャッジ時間 | 17,908 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 50 |
ソースコード
use std::collections::{HashSet, VecDeque}; fn main() { let (n, m) = input_tuple(); let u_v = input_tuple_vec::<usize>(m); let mut list = vec![Vec::new(); n]; for &(u, v) in &u_v { list[u - 1].push(v - 1); } let start = (0, false, false); // ---------------------------------- // let mut visited = vec![false; n]; let mut visited = HashSet::new(); let mut queue = VecDeque::new(); queue.push_back((start, 0)); visited.insert(start); // let mut steps = vec![usize::MAX; n]; // steps[start] = 0; while let Some(((current, visit_n, visit_n_1), step)) = queue.pop_front() { if current == 0 && visit_n && visit_n_1 { println!("{}", step); return; } let mut next_visit_n = visit_n; let mut next_visit_n_1 = visit_n_1; if current == n - 1 { next_visit_n = true; } if current == n - 2 { next_visit_n_1 = true; } for &next in list[current].iter() { if visited.contains(&(next, next_visit_n, next_visit_n_1)) { continue; } // 次へ visited.insert((next, next_visit_n, next_visit_n_1)); queue.push_back(((next, next_visit_n, next_visit_n_1), step + 1)); } } println!("-1"); } fn input_tuple<T>() -> (T, T) where T: std::str::FromStr, <T as std::str::FromStr>::Err: std::fmt::Debug, { let stdin = std::io::stdin(); let mut buf = String::new(); stdin.read_line(&mut buf).unwrap(); buf = buf.trim_end().to_owned(); let mut iter = buf.split_whitespace(); let n = iter.next().unwrap().parse().unwrap(); let m = iter.next().unwrap().parse().unwrap(); (n, m) } fn input_tuple_vec<T>(n: usize) -> Vec<(T, T)> where T: std::str::FromStr, <T as std::str::FromStr>::Err: std::fmt::Debug, { // タプルのベクタ let stdin = std::io::stdin(); let mut s_t_d = Vec::with_capacity(n); for _ in 0..n { let mut buf = String::new(); stdin.read_line(&mut buf).unwrap(); buf = buf.trim_end().to_owned(); let mut iter = buf.split_whitespace(); let s = iter.next().unwrap().parse().unwrap(); let t = iter.next().unwrap().parse().unwrap(); // let d = iter.next().unwrap().parse().unwrap(); s_t_d.push((s, t)); } s_t_d }