#994822 (Rust) No.2805 Go to School

• 問題: No.2805 Go to School
• ユーザー: naut3
• 提出日時: 2024-07-13 12:13:31
• 言語: Rust (1.77.0 + proconio)
• 結果: AC
• 実行時間: 221 ms / 2,000 ms
• コード長: 5,211 bytes
• コンパイル時間: 15,537 ms
• コンパイル使用メモリ: 397,616 KB
• 実行使用メモリ: 29,156 KB
• 最終ジャッジ日時: 2024-07-16 01:42:23
• 合計ジャッジ時間: 15,935 ms
• ジャッジサーバーID （参考情報）: judge2 / judge3

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	1 ms; 6,812 KB
testcase_01	AC	1 ms; 6,816 KB
testcase_02	AC	1 ms; 6,944 KB
testcase_03	AC	1 ms; 6,940 KB
testcase_04	AC	56 ms; 21,324 KB
testcase_05	AC	70 ms; 19,764 KB
testcase_06	AC	42 ms; 10,624 KB
testcase_07	AC	36 ms; 11,520 KB
testcase_08	AC	53 ms; 20,544 KB
testcase_09	AC	43 ms; 10,752 KB
testcase_10	AC	34 ms; 12,160 KB
testcase_11	AC	221 ms; 28,592 KB
testcase_12	AC	97 ms; 17,136 KB
testcase_13	AC	148 ms; 22,968 KB
testcase_14	AC	18 ms; 6,944 KB
testcase_15	AC	1 ms; 6,940 KB
testcase_16	AC	1 ms; 6,944 KB
testcase_17	AC	1 ms; 6,944 KB
testcase_18	AC	59 ms; 13,824 KB
testcase_19	AC	38 ms; 9,472 KB
testcase_20	AC	91 ms; 20,176 KB
testcase_21	AC	183 ms; 29,156 KB
testcase_22	AC	65 ms; 13,736 KB
testcase_23	AC	96 ms; 17,296 KB
testcase_24	AC	89 ms; 17,288 KB
testcase_25	AC	30 ms; 10,044 KB
testcase_26	AC	153 ms; 29,104 KB
testcase_27	AC	56 ms; 22,308 KB
testcase_28	AC	5 ms; 6,940 KB
testcase_29	AC	9 ms; 6,940 KB
testcase_30	AC	26 ms; 14,528 KB
testcase_31	AC	42 ms; 12,040 KB
testcase_32	AC	78 ms; 24,020 KB
testcase_33	AC	125 ms; 23,684 KB
testcase_34	AC	1 ms; 6,944 KB
testcase_35	AC	1 ms; 6,940 KB
testcase_36	AC	43 ms; 10,568 KB
testcase_37	AC	49 ms; 14,000 KB
testcase_38	AC	109 ms; 23,032 KB

ソースコード

#![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<W> {
        pub size: usize,
        pub adjacency_list: Vec<Vec<(usize, W)>>,
    }

    impl<W: Clone> DirectedGraph<W> {
        /// 頂点数が 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<W> Graph for DirectedGraph<W> {
        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<W> {
        pub size: usize,
        pub adjacency_list: Vec<Vec<(usize, W)>>,
    }

    impl<W: Clone> UndirectedGraph<W> {
        /// 頂点数が 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<W: Clone> Graph for UndirectedGraph<W> {
        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<Output = W> + PartialOrd + Ord + Default + Clone + Copy + 'static,
    >(
        graph: &dyn Graph<Weight = W>,
        source: usize,
    ) -> Vec<Option<W>> {
        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;
    }
}