#![allow(non_snake_case)] #[allow(unused_imports)] use proconio::{fastout, input, marker::*}; #[fastout] fn main() { input! { N: usize, M: usize, L: usize, S: usize, E: usize, edges: [(Usize1, Usize1, usize); M], T: [Usize1; L], } let graph = { let mut graph = graph::UndirectedGraph::new(N); for (u, v, w) in edges { graph.add_edge(u, v, w); } graph }; let dist_src = dijkstras_algorithm::dijkstras_algorithm(&graph, 0); let dist_dst = dijkstras_algorithm::dijkstras_algorithm(&graph, N - 1); let mut ans = 1 << 60; for t in T { if let Some(d1) = dist_src[t] { if let Some(d2) = dist_dst[t] { let d1 = if d1 < S { S } else if d1 < S + E { d1 } else { 1 << 60 }; ans = std::cmp::min(ans, d1 + d2 + 1); } } } if ans >= 1 << 60 { println!("-1"); } else { println!("{}", ans); } } pub mod graph { /// グラフ pub trait Graph { type Weight; fn size(&self) -> usize; fn add_edge(&mut self, u: usize, v: usize, w: Self::Weight); fn adjacent(&self, v: usize) -> &[(usize, Self::Weight)]; } /// 有向グラフ #[derive(Clone)] pub struct DirectedGraph { pub size: usize, pub adjacency_list: Vec>, } impl DirectedGraph { /// 頂点数が size の有向グラフを新たに生成する pub fn new(size: usize) -> Self { return Self { size, adjacency_list: vec![vec![]; size], }; } /// u から v への重み w の有向辺を追加する pub fn add_edge(&mut self, u: usize, v: usize, w: W) { self.adjacency_list[u].push((v, w)); } /// 頂点 v の隣接リストを返す pub fn adjacent(&self, v: usize) -> &[(usize, W)] { &self.adjacency_list[v] } } impl Graph for DirectedGraph { type Weight = W; fn size(&self) -> usize { self.size } fn add_edge(&mut self, u: usize, v: usize, w: Self::Weight) { self.adjacency_list[u].push((v, w)); } fn adjacent(&self, v: usize) -> &[(usize, W)] { &self.adjacency_list[v] } } /// 無向グラフ #[derive(Clone)] pub struct UndirectedGraph { pub size: usize, pub adjacency_list: Vec>, } impl UndirectedGraph { /// 頂点数が size の無向グラフを新たに生成する pub fn new(size: usize) -> Self { return Self { size, adjacency_list: vec![vec![]; size], }; } /// u と v の間に重み w の辺を追加する pub fn add_edge(&mut self, u: usize, v: usize, w: W) { self.adjacency_list[u].push((v, w.clone())); self.adjacency_list[v].push((u, w)); } /// 頂点 v の隣接リストを返す pub fn adjacent(&self, v: usize) -> &[(usize, W)] { &self.adjacency_list[v] } } impl Graph for UndirectedGraph { type Weight = W; fn size(&self) -> usize { self.size } fn add_edge(&mut self, u: usize, v: usize, w: Self::Weight) { self.adjacency_list[u].push((v, w.clone())); self.adjacency_list[v].push((u, w)); } fn adjacent(&self, v: usize) -> &[(usize, W)] { &self.adjacency_list[v] } } } pub mod dijkstras_algorithm { use crate::graph::Graph; pub fn dijkstras_algorithm< W: Sized + std::ops::Add + PartialOrd + Ord + Default + Clone + Copy + 'static, >( graph: &dyn Graph, source: usize, ) -> Vec> { assert!(source < graph.size()); let mut dist = vec![None; graph.size()]; dist[source] = Some(W::default()); let mut seen = vec![false; graph.size()]; let mut hq = std::collections::BinaryHeap::default(); hq.push((std::cmp::Reverse(W::default()), source)); while let Some((_, u)) = hq.pop() { if seen[u] { continue; } seen[u] = true; for &(v, w) in graph.adjacent(u) { if !seen[v] { let d = dist[u].unwrap() + w; match dist[v] { Some(pd) => { if d < pd { dist[v] = Some(d); hq.push((std::cmp::Reverse(d), v)); } } None => { dist[v] = Some(d); hq.push((std::cmp::Reverse(d), v)); } } } } } return dist; } }