use std::io::Read; use std::cmp::Ordering; use std::collections::BinaryHeap; #[derive(Copy, Clone)] struct State { cost: f64, pos: usize, } impl PartialOrd for State { fn partial_cmp(&self, other: &Self) -> Option { other.cost.partial_cmp(&self.cost) } } impl PartialEq for State { fn eq(&self, other: &Self) -> bool { self.cost == other.cost } } impl Ord for State { fn cmp(&self, other: &Self) -> Ordering { self.partial_cmp(&other).unwrap() } } impl Eq for State {} fn main() { let mut buf = String::new(); std::io::stdin().read_to_string(&mut buf).unwrap(); let mut iter = buf.split_whitespace(); let n: usize = iter.next().unwrap().parse().unwrap(); let m: usize = iter.next().unwrap().parse().unwrap(); let x = iter.next().unwrap().parse::().unwrap() - 1; let y = iter.next().unwrap().parse::().unwrap() - 1; let mut pole: Vec<(i64, i64)> = Vec::with_capacity(n); for _ in 0..n { let p: i64 = iter.next().unwrap().parse().unwrap(); let q: i64 = iter.next().unwrap().parse().unwrap(); pole.push((p, q)); } let mut g: Vec> = vec![Vec::new(); n]; for _ in 0..m { let i = iter.next().unwrap().parse::().unwrap() - 1; let j = iter.next().unwrap().parse::().unwrap() - 1; let dx = pole[i].0 - pole[j].0; let dy = pole[i].1 - pole[j].1; let cost = ((dx * dx + dy * dy) as f64).sqrt(); g[i].push((cost, j)); g[j].push((cost, i)); } let mut dist: Vec = vec![f64::MAX; n]; let mut heap = BinaryHeap::new(); dist[x] = 0.0; heap.push(State { cost: 0.0, pos: x }); while let Some(State { cost, pos }) = heap.pop() { for edge in &g[pos] { let next = State { cost: cost + edge.0, pos: edge.1}; if next.cost < dist[next.pos] { heap.push(next); dist[next.pos] = next.cost; } } } println!("{}", dist[y]); }