結果

問題 No.2805 Go to School
コンテスト
ユーザー naut3
提出日時 2024-07-13 12:13:31
言語 Rust
(1.83.0 + proconio)
結果
AC  
実行時間 172 ms / 2,000 ms
コード長 5,211 bytes
コンパイル時間 11,261 ms
コンパイル使用メモリ 386,680 KB
実行使用メモリ 29,280 KB
最終ジャッジ日時 2025-04-09 15:41:26
合計ジャッジ時間 14,873 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 36
権限があれば一括ダウンロードができます

ソースコード

diff # 

#![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;
    }
}
0