結果

問題 No.807 umg tours
ユーザー niuezniuez
提出日時 2019-03-29 16:33:30
言語 Rust
(1.77.0)
結果
AC  
実行時間 490 ms / 4,000 ms
コード長 6,332 bytes
コンパイル時間 3,598 ms
コンパイル使用メモリ 151,484 KB
実行使用メモリ 89,080 KB
最終ジャッジ日時 2023-08-15 12:16:56
合計ジャッジ時間 9,659 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 4 ms
6,828 KB
testcase_01 AC 4 ms
6,900 KB
testcase_02 AC 4 ms
7,152 KB
testcase_03 AC 3 ms
6,992 KB
testcase_04 AC 3 ms
6,872 KB
testcase_05 AC 2 ms
6,816 KB
testcase_06 AC 3 ms
7,140 KB
testcase_07 AC 3 ms
6,952 KB
testcase_08 AC 3 ms
6,700 KB
testcase_09 AC 3 ms
6,792 KB
testcase_10 AC 2 ms
6,756 KB
testcase_11 AC 233 ms
71,492 KB
testcase_12 AC 277 ms
53,008 KB
testcase_13 AC 347 ms
73,692 KB
testcase_14 AC 141 ms
36,156 KB
testcase_15 AC 111 ms
30,004 KB
testcase_16 AC 370 ms
78,076 KB
testcase_17 AC 490 ms
88,204 KB
testcase_18 AC 490 ms
87,804 KB
testcase_19 AC 470 ms
86,608 KB
testcase_20 AC 286 ms
46,572 KB
testcase_21 AC 303 ms
48,968 KB
testcase_22 AC 120 ms
24,732 KB
testcase_23 AC 86 ms
21,176 KB
testcase_24 AC 268 ms
68,960 KB
testcase_25 AC 475 ms
89,080 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

use std::ops::{Index, IndexMut};

pub trait Zero {
    fn zero() -> Self;
}

impl Zero for usize { fn zero() -> Self { 0 } }
impl Zero for isize { fn zero() -> Self { 0 } }

pub trait Property: Copy + Zero {}

impl<P> Property for P where P: Copy + Zero {}

pub trait Weight: Property + std::ops::Add<Output=Self> + std::cmp::Ord {}

impl<W> Weight for W where W: Property + std::ops::Add<Output=W> + std::cmp::Ord {}

pub trait NNWeight: Weight {}

impl NNWeight for usize {}

pub trait ID {
    fn id(&self) -> usize;
}

pub struct Properties<W: Copy> {
    vec: Vec<W>
}

impl<'a, I: ID, W: Copy> Index<&'a I> for Properties<W> {
    type Output = W;
    fn index(&self, idx: &'a I) -> & Self::Output { &self.vec[idx.id()] }
}

impl<'a, I: ID, W: Copy> IndexMut<&'a I> for Properties<W> {
    fn index_mut(&mut self, idx: &'a I) -> &mut Self::Output { &mut self.vec[idx.id()] }
}

impl<'a, W: Copy> Properties<W> {
    pub fn new(n: usize, init: &W) -> Self {
        Properties {
           vec: vec![*init; n], 
        }
    }
    pub fn iter(&'a self) -> std::slice::Iter<'a, W> { self.vec.iter() }
}

#[derive(Clone,Copy,Eq,PartialEq,Debug)]
pub struct Eite(pub usize);

pub trait Vertex: ID + Clone { }

impl<V: ID + Clone> Vertex for V { }

pub trait Edge {
    type VType: Vertex;
    fn from(&self) -> &Self::VType;
    fn to(&self) -> &Self::VType;
}

pub struct IEdge<E: Edge>(E, usize);

impl<E: Edge> ID for IEdge<E> {
    fn id(&self) -> usize { self.1 }
}

impl<E: Edge> IEdge<E> {
    pub fn from(&self) -> &E::VType { self.0.from() }
    pub fn to(&self) -> &E::VType { self.0.to() }
    pub fn edge(&self) -> &E { &self.0 }
}

pub struct AdjIter<'a, E: Edge + 'a> {
    iter: std::slice::Iter<'a, Eite>,
    edges: &'a Vec<IEdge<E>>,
}

impl<'a, E: Edge + 'a> std::iter::Iterator for AdjIter<'a, E> {
    type Item = &'a IEdge<E>;
    fn next(&mut self) -> Option<Self::Item> {
        match self.iter.next() {
            Some(ei) => {
                Some( &self.edges[ei.0] )
            }
            None => {
                None
            }
        }
    }
}

pub trait Graph<'a, V, E>: where V: Vertex, E: Edge<VType=V> + 'a {
    fn add_edge(&mut self, e: E);
    fn delta(&'a self, v: &V) -> AdjIter<E>;
    fn v_size(&self) -> usize;
    fn e_size(&self) -> usize;
}

pub struct DirectedGraph<V: Vertex, E: Edge<VType=V>> {
    n: usize,
    m: usize,
    g: Vec<Vec<Eite>>,
    es: Vec<IEdge<E>>,
}

impl<'a, V, E> Graph<'a,V,E> for DirectedGraph<V,E> where V: Vertex, E: Edge<VType=V> + 'a {
    fn add_edge(&mut self, e: E) {
        let ei = Eite(self.m);
        self.m += 1;
        self.g[e.from().id()].push(ei);
        self.es.push(IEdge(e, ei.0));
    }
    fn delta(&'a self, v: &V) -> AdjIter<'a, E> {
        AdjIter { iter: self.g[v.id()].iter(), edges: &self.es }
    }
    fn v_size(&self) -> usize {
        self.n
    }
    fn e_size(&self) -> usize {
        self.m
    }
}

impl<V: Vertex, E: Edge<VType=V>> DirectedGraph<V,E> {
    pub fn new(n: usize) -> Self {
        DirectedGraph {
            n: n,
            m: 0,
            g: vec![Vec::<Eite>::new(); n],
            es: Vec::new(),
        }
    }
}

use std::collections::BinaryHeap;
use std::cmp::Ordering;

struct DijkstraNode<W: NNWeight, V: Vertex> {
    dist: Option<W>,
    ver : V,
}

impl<W: NNWeight, V: Vertex> Ord for DijkstraNode<W, V> {
    fn cmp(&self, other: &Self) -> Ordering {
        other.dist.cmp(&self.dist)
    }
}
impl<W: NNWeight, V: Vertex> PartialOrd for DijkstraNode<W, V> {
    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
        Some(other.dist.cmp(&self.dist))
    }
}
impl<W: NNWeight, V: Vertex> PartialEq for DijkstraNode<W, V> {
    fn eq(&self, other: &Self) -> bool {
        self.dist == other.dist
    }
}

impl<W: NNWeight, V: Vertex> Eq for DijkstraNode<W, V> { }


pub fn dijkstra<'a, V, E, G, W, F>(g: &'a G, s: &V, cost: F) -> Properties<Option<W>>
where V: Vertex, E: Edge<VType=V> + 'a, G: Graph<'a, V, E>, W: NNWeight, F: Fn(&E) -> W { 

    let n = g.v_size();
    let mut dist = Properties::new(n, &None);
    dist[s] = Some(W::zero());

    let mut heap = BinaryHeap::new();
    heap.push(DijkstraNode { dist: dist[s], ver: s.clone() });

    while let Some(DijkstraNode { dist: Some(d), ver: v}) = heap.pop() {
        if let Some(now) = dist[&v] {
            if now < d { continue }
        }
        for e in g.delta(&v) {
            if match dist[e.to()] {
                Some(d2) => { 
                    cost(e.edge()) + d < d2
                }
                None => true
            } {
                dist[e.to()] = Some(cost(e.edge()) + d);
                heap.push(DijkstraNode{ dist: dist[e.to()], ver: e.to().clone() })
            }
        }
    }

    dist
}

// solution

#[derive(Clone)]
enum VIP {
    Yet,
    Used,
}

#[derive(Clone)]
struct Ver(usize, VIP);

impl ID for Ver {
    fn id(&self) -> usize {
        self.0 + match self.1 { 
            VIP::Yet => 0,
            VIP::Used => 100000,
        }
    }
} 
impl Edge for (Ver, Ver, usize) {
    type VType = Ver;
    fn from(&self) -> &Self::VType { &self.0 }
    fn to(&self) -> &Self::VType { &self.1 }
}



fn main() {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).unwrap();
    let v:Vec<usize> = s.trim().split_whitespace()
        .map(|e|e.parse().unwrap()).collect();
    let (n, m) = (v[0] , v[1]);
    let mut g = DirectedGraph::new(200000);

    for _ in 0..m{
        let mut t = String::new();
        std::io::stdin().read_line(&mut t).unwrap();
        let x:Vec<usize> = t.trim().split_whitespace()
            .map(|e|e.parse().unwrap()).collect();
        let (v, u, d) = (x[0] - 1, x[1] - 1, x[2]);
        g.add_edge((Ver(v, VIP::Yet), Ver(u, VIP::Yet), d));
        g.add_edge((Ver(v, VIP::Used), Ver(u, VIP::Used), d));
        g.add_edge((Ver(v, VIP::Yet), Ver(u, VIP::Used), 0));
        g.add_edge((Ver(u, VIP::Yet), Ver(v, VIP::Yet), d));
        g.add_edge((Ver(u, VIP::Used), Ver(v, VIP::Used), d));
        g.add_edge((Ver(u, VIP::Yet), Ver(v, VIP::Used), 0));
    }
    g.add_edge((Ver(0, VIP::Yet), Ver(0, VIP::Used), 0));

    let res = dijkstra(&g, &Ver(0, VIP::Yet), |ep| ep.2);
    for i in 0..n {
        println!("{}", res[&Ver(i, VIP::Yet)].unwrap() + res[&Ver(i, VIP::Used)].unwrap());
    }
}
0