use std::collections::binary_heap::BinaryHeap; use std::cmp::{min, Ordering, Reverse}; macro_rules! input { (source = $s:expr, $($r:tt)*) => { let mut iter = $s.split_whitespace(); let mut next = || { iter.next().unwrap() }; input_inner!{next, $($r)*} }; ($($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::>() }; ($next:expr, chars) => { read_value!($next, String).chars().collect::>() }; ($next:expr, usize1) => { read_value!($next, usize) - 1 }; ($next:expr, $t:ty) => { $next().parse::<$t>().expect("Parse error") }; } #[derive(Debug, Clone, Copy)] struct Edge { to: usize, cost: i32, } #[derive(Debug, Clone, Copy, PartialEq, Eq)] struct Node { id: usize, cost: i32, prev: Option, } #[derive(Debug)] struct Graph { nodes: Vec, edges: Vec>, } impl Graph { fn new(n_nodes: usize) -> Self { let mut nodes = Vec::with_capacity(n_nodes); let edges = vec![Vec::new(); n_nodes]; for i in 0..n_nodes { nodes.push(Node { id: i, cost: i32::MAX, prev: None }) } Self { nodes, edges, } } fn add_edge(&mut self, from: usize, to: usize, cost: i32) { self.edges[from].push(Edge { to, cost }); self.edges[to].push(Edge { to: from, cost }); } } impl PartialOrd for Node { fn partial_cmp(&self, other: &Self) -> Option { self.cost.partial_cmp(&other.cost) } } impl Ord for Node { fn cmp(&self, other: &Self) -> Ordering { self.cost.cmp(&other.cost) } } fn dijkstra(graph: &mut Graph, from: usize, to: usize) { let mut heap = BinaryHeap::new(); let mut visited = vec![false; graph.nodes.len()]; graph.nodes[from].cost = 0; heap.push(Reverse(graph.nodes[from])); while let Some(Reverse(node)) = heap.pop() { if visited[node.id] { continue; } visited[node.id] = true; if node.id == to { break; } for e in &graph.edges[node.id] { if node.cost + e.cost < graph.nodes[e.to].cost { graph.nodes[e.to].cost = node.cost + e.cost; graph.nodes[e.to].prev = Some(node.id); heap.push(Reverse(graph.nodes[e.to])); } if node.cost + e.cost == graph.nodes[e.to].cost { if let Some(prev_node_id) = graph.nodes[e.to].prev { graph.nodes[e.to].prev = Some(min(prev_node_id, node.id)); } } } } } fn backtrace_path(graph: &Graph, to: usize) -> Vec<&Node> { let mut path = Vec::new(); let mut node_id = to; loop { let node = &graph.nodes[node_id]; path.push(node); if let Some(prev_node_id) = node.prev { node_id = prev_node_id; } else { break; } } path.reverse(); path } fn main() { input! { n: usize, m: usize, s: usize, g: usize, edges: [(usize, usize, i32); m] } let mut graph = Graph::new(n); for (from, to, cost) in edges { graph.add_edge(from, to, cost); } dijkstra(&mut graph, s, g); let path = backtrace_path(&graph, g); let answer = path.iter().map(|p| p.id.to_string()).collect::>().join(" "); println!("{}", answer); }