結果
問題 |
No.1190 Points
|
ユーザー |
|
提出日時 | 2023-04-23 10:53:26 |
言語 | Rust (1.83.0 + proconio) |
結果 |
AC
|
実行時間 | 220 ms / 2,000 ms |
コード長 | 3,398 bytes |
コンパイル時間 | 15,192 ms |
コンパイル使用メモリ | 377,732 KB |
実行使用メモリ | 24,832 KB |
最終ジャッジ日時 | 2024-11-07 18:45:06 |
合計ジャッジ時間 | 18,499 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 25 |
ソースコード
use std::collections::VecDeque; fn main() { let (n, m, p) = { let mut line = String::new(); std::io::stdin().read_line(&mut line).unwrap(); let mut iter = line.split_whitespace(); ( iter.next().unwrap().parse::<usize>().unwrap(), iter.next().unwrap().parse::<usize>().unwrap(), iter.next().unwrap().parse::<usize>().unwrap(), ) }; let (s, g) = { let mut line = String::new(); std::io::stdin().read_line(&mut line).unwrap(); let mut iter = line.split_whitespace(); ( iter.next().unwrap().parse::<usize>().unwrap() - 1, iter.next().unwrap().parse::<usize>().unwrap() - 1, ) }; let uv: Vec<_> = (0..m) .map(|_| { let mut line = String::new(); std::io::stdin().read_line(&mut line).unwrap(); let mut iter = line.split_whitespace(); ( iter.next().unwrap().parse::<usize>().unwrap() - 1, iter.next().unwrap().parse::<usize>().unwrap() - 1, ) }) .collect(); let mut graph = vec![vec![]; n]; for &(a, b) in &uv { graph[a].push(b); graph[b].push(a); } graph.iter_mut().for_each(|x| x.sort_unstable()); let mut distances: Vec<Vec<Option<usize>>> = vec![vec![None; 2]; n]; distances[s][0] = Some(0); let mut queue = VecDeque::from(vec![s]); while let Some(cur) = queue.pop_front() { for &next in &graph[cur] { for cur_parity in 0..2 { let next_parity = 1 - cur_parity; if let Some(cur_dist) = distances[cur][cur_parity] { let next_dist = &mut distances[next][next_parity]; if next_dist.is_none() || cur_dist + 1 < next_dist.unwrap() { *next_dist = Some(cur_dist + 1); queue.push_back(next); } } } } } let mut rev_distances: Vec<Vec<Option<usize>>> = vec![vec![None; 2]; n]; rev_distances[g][0] = Some(0); let mut queue = VecDeque::from(vec![g]); while let Some(cur) = queue.pop_front() { for &next in &graph[cur] { for cur_parity in 0..2 { let next_parity = 1 - cur_parity; if let Some(cur_dist) = rev_distances[cur][cur_parity] { let next_dist = &mut rev_distances[next][next_parity]; if next_dist.is_none() || cur_dist + 1 < next_dist.unwrap() { *next_dist = Some(cur_dist + 1); queue.push_back(next); } } } } } let mut flags = vec![false; n]; let p_parity = p % 2; for i in 0..n { for parity1 in 0..2 { let parity2 = (p_parity + parity1) % 2; if let (Some(dist1), Some(dist2)) = (distances[i][parity1], rev_distances[i][parity2]) { if dist1 + dist2 <= p { flags[i] = true; } } } } let ans_num = flags.iter().filter(|&&x| x).count(); if ans_num == 0 { println!("-1"); std::process::exit(0); } println!("{}", ans_num); for i in (0..n).filter(|&i| flags[i]) { println!("{}", i + 1); } }