結果
問題 | No.2565 はじめてのおつかい |
ユーザー |
![]() |
提出日時 | 2023-11-27 16:46:52 |
言語 | Rust (1.83.0 + proconio) |
結果 |
AC
|
実行時間 | 46 ms / 2,000 ms |
コード長 | 2,353 bytes |
コンパイル時間 | 14,214 ms |
コンパイル使用メモリ | 377,968 KB |
実行使用メモリ | 12,800 KB |
最終ジャッジ日時 | 2024-09-26 12:29:38 |
合計ジャッジ時間 | 17,413 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 50 |
ソースコード
use std::vec;macro_rules! input {($($r:tt)*) => {let stdin = std::io::stdin();let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));let mut next = move || -> String{bytes.by_ref().map(|r|r.unwrap() as char).skip_while(|c|c.is_whitespace()).take_while(|c|!c.is_whitespace()).collect()};input_inner!{next, $($r)*}};}macro_rules! input_inner {($next:expr) => {};($next:expr,) => {};($next:expr, $var:ident : $t:tt $($r:tt)*) => {let $var = read_value!($next, $t);input_inner!{$next $($r)*}};}macro_rules! read_value {($next:expr, ( $($t:tt),* )) => { ($(read_value!($next, $t)),*) };($next:expr, [ $t:tt ; $len:expr ]) => {(0..$len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()};($next:expr, $t:ty) => ($next().parse::<$t>().expect("Parse error"));}fn main() {input! {n: usize,m: usize,edges: [(usize, usize); m],}let graph = {let mut graph = vec![vec![]; n];for &(a, b) in &edges {let a = a - 1;let b = b - 1;graph[a].push(b);}graph};let inf = 998244353;let get_dist = |start: usize| -> Vec<usize> {let mut dist = vec![inf; n];dist[start] = 0;let mut queue = std::collections::VecDeque::new();queue.push_back(start);while let Some(v) = queue.pop_front() {let d = dist[v];for &e in &graph[v] {if dist[e] <= d + 1 {continue;}dist[e] = d + 1;queue.push_back(e);}}dist};let dist_st = get_dist(0);let dist_a = get_dist(n - 2);let dist_b = get_dist(n - 1);let st_to_a = dist_st[n - 2];let st_to_b = dist_st[n - 1];let a_to_b = dist_a[n - 1];let a_to_st = dist_a[0];let b_to_a = dist_b[n - 2];let b_to_st = dist_b[0];let ans = {let ans = (st_to_a + a_to_b + b_to_st).min(st_to_b + b_to_a + a_to_st);let mut ans = ans as i64;if ans >= inf as i64 {ans = -1;}ans};println!("{}", ans);}