結果

問題 No.807 umg tours
コンテスト
ユーザー niuez
提出日時 2019-04-10 23:58:54
言語 Rust
(1.83.0 + proconio)
結果
TLE  
(最新)
AC  
(最初)
実行時間 -
コード長 12,727 bytes
コンパイル時間 14,782 ms
コンパイル使用メモリ 378,892 KB
実行使用メモリ 94,964 KB
最終ジャッジ日時 2024-07-08 09:57:55
合計ジャッジ時間 41,495 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 25 TLE * 1
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

impl Zero for usize { fn zero() -> Self { 0 } }
impl Zero for u8 { fn zero() -> Self { 0 } }
impl Zero for u16 { fn zero() -> Self { 0 } }
impl Zero for u32 { fn zero() -> Self { 0 } } impl Zero for u64 { fn zero() -> Self { 0 } } impl Zero for isize { fn zero() -> Self { 0 } }
impl Zero for i8 { fn zero() -> Self { 0 } }
impl Zero for i16 { fn zero() -> Self { 0 } }
impl Zero for i32 { fn zero() -> Self { 0 } }
impl Zero for i64 { fn zero() -> Self { 0 } }

pub trait IsNN {}

impl IsNN for usize {}
impl IsNN for u8 {}
impl IsNN for u16 {}
impl IsNN for u32 {}
impl IsNN for u64 {}

pub trait Property: Copy {}

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

pub trait ArbWeight: Property + std::ops::Add<Output=Self> + std::ops::Sub<Output=Self> + std::cmp::Ord {
    fn zero() -> Self;
    fn inf() -> Self;
    fn neg_inf() -> Self { unreachable!() }
}

pub trait NNegWeight: ArbWeight {}

#[derive(Clone, Copy, PartialEq, Eq)]
pub enum NNegW<W> where W: Zero + IsNN + std::ops::Add<Output=W> + std::ops::Sub<Output=W> + std::cmp::Ord + Copy {
    Inf,
    Some(W), 
}

impl<W> std::ops::Add for NNegW<W> where W: Zero + IsNN + std::ops::Add<Output=W> + std::ops::Sub<Output=W> + std::cmp::Ord + Copy {
    type Output = Self;
    fn add(self, rhs: Self) -> Self {
        match self {
            NNegW::Inf => {
                NNegW::Inf
            }
            NNegW::Some(d) => {
                match rhs {
                    NNegW::Inf => NNegW::Inf,
                    NNegW::Some(d2) => NNegW::Some(d + d2),
                }
            }
        }
    }

}

impl<W> std::ops::Sub for NNegW<W> where W: Zero + IsNN + std::ops::Add<Output=W> + std::ops::Sub<Output=W> + std::cmp::Ord + Copy {
    type Output = Self;
    fn sub(self, rhs: Self) -> Self {
        match self {
            NNegW::Inf => {
                match rhs {
                    NNegW::Inf => unreachable!(),
                    _ => NNegW::Inf,
                }
            }
            NNegW::Some(d) => {
                match rhs {
                    NNegW::Inf => unreachable!(), 
                    NNegW::Some(d2) => NNegW::Some(d - d2),
                }
            }
        }
    }
}


impl<W> std::cmp::PartialOrd for NNegW<W> where W: Zero + IsNN + std::ops::Add<Output=W> + std::ops::Sub<Output=W> + std::cmp::Ord + Copy {
    fn partial_cmp(&self, rhs: &Self) -> Option<std::cmp::Ordering> {
        Some(self.cmp(rhs))
    }
}

impl<W> std::cmp::Ord for NNegW<W> where W: Zero + IsNN + std::ops::Add<Output=W> + std::ops::Sub<Output=W> + std::cmp::Ord + Copy {
    fn cmp(&self, rhs: &Self) -> std::cmp::Ordering {
        match self {
            NNegW::Inf => {
                match rhs {
                    NNegW::Inf => unreachable!(),
                    _ => std::cmp::Ordering::Greater,
                }
            }
            NNegW::Some(d) => {
                match rhs {
                    NNegW::Inf => std::cmp::Ordering::Less,
                    NNegW::Some(d2) => d.cmp(d2), 
                }
            }
        }
    }
}

impl std::ops::Shl for NNegW<usize> {
    type Output = Self;
    fn shl(self, rhs: Self) -> Self {
        match rhs {
            NNegW::Some(r) => match self {
                NNegW::Some(d) => NNegW::Some(d.shl(r)), 
                other => other, 
            }
            _ => unreachable!(), 
        }
    }
}

impl std::ops::Shr for NNegW<usize> {
    type Output = Self;
    fn shr(self, rhs: Self) -> Self {
        match rhs {
            NNegW::Some(r) => match self {
                NNegW::Some(d) => NNegW::Some(d.shr(r)), 
                other => other, 
            }
            _ => unreachable!(), 
        }
    }
}


impl<W> ArbWeight for NNegW<W> where W: Zero + IsNN + std::ops::Add<Output=W> + std::ops::Sub<Output=W> + std::cmp::Ord + Copy {
    fn zero() -> Self { NNegW::Some(W::zero()) }
    fn inf() -> Self { NNegW::Inf }
}

impl<W> NNegWeight for NNegW<W> where W: Zero + IsNN + std::ops::Add<Output=W> + std::ops::Sub<Output=W> + std::cmp::Ord + Copy {}

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

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

impl ID for usize {
    fn id(&self) -> usize { *self }
}

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() }
}

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;
}

impl<V> Edge for (V, V) where V: Vertex { 
    type VType = V;
    fn from(&self) -> &Self::VType { &self.0 }
    fn to(&self) -> &Self::VType { &self.1 }
}

impl<V, P> Edge for (V, V, P) where V: Vertex, P: Property { 
    type VType = V;
    fn from(&self) -> &Self::VType { &self.0 }
    fn to(&self) -> &Self::VType { &self.1 }
}

pub trait AdjEdge<V, E>: ID where V: Vertex, E: Edge<VType=V> {
    fn from(&self) -> &V;
    fn to(&self) -> &V;
    fn edge(&self) -> &E;
}

pub trait Graph<'a, V, E, AE> where V: Vertex + 'a, E: Edge<VType=V> + 'a, AE: AdjEdge<V, E> {
    type AdjIter: std::iter::Iterator<Item=AE>;
    type EIter: std::iter::Iterator<Item=AE>;
    type VIter: std::iter::Iterator<Item=V>;
    fn add_edge(&mut self, e: E);
    fn delta(&'a self, v: &V) -> Self::AdjIter;
    fn edges(&'a self) -> Self::EIter;
    fn vertices(&'a self) -> Self::VIter;
    fn v_size(&self) -> usize;
    fn e_size(&self) -> usize;
}

pub trait Directed<'a, V, E, AE>: Graph<'a, V, E, AE> where V: Vertex + 'a, E: Edge<VType=V> + 'a, AE: AdjEdge<V, E> {}
pub trait Undirected<'a, V, E, AE>: Graph<'a, V, E, AE> where V: Vertex + 'a, E: Edge<VType=V> + 'a, AE: AdjEdge<V, E> {}

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

pub struct DiAdjEdge<'a, E: Edge + 'a>(&'a E, usize);

impl<'a, E: Edge + 'a> ID for DiAdjEdge<'a, E> {
    fn id(&self) -> usize { self.1 }
}

impl<'a, V, E> AdjEdge<V, E> for DiAdjEdge<'a, E> where V: Vertex, E: Edge<VType=V> + 'a {
    fn from(&self) -> &E::VType { self.0.from() }
    fn to(&self) -> &E::VType { self.0.to() }
    fn edge(&self) -> &E { self.0 }
}

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

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

pub struct EIter<'a, E: Edge + 'a> {
    i: usize,
    iter: std::slice::Iter<'a, E>,
}

impl<'a, E: Edge + 'a> std::iter::Iterator for EIter<'a, E> {
    type Item = DiAdjEdge<'a, E>;
    fn next(&mut self) -> Option<Self::Item> {
        match self.iter.next() {
            Some(e) => {
                let i = self.i;
                self.i += 1;
                Some(DiAdjEdge(&e, i))
            }
            None => None
        }
    }
}

pub struct VIter<'a, V: Vertex + 'a> {
    iter: std::slice:: Iter<'a, Option<V>>,
}

impl<'a, V: Vertex + 'a> std::iter::Iterator for VIter<'a, V> {
    type Item = V;
    fn next(&mut self) -> Option<Self::Item> {
        while let Some(v) = self.iter.next() {
            if v.is_none() { continue; }
            else { return v.clone(); }
        }
        None
    }
}

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

impl<'a, V, E> Graph<'a,V,E,DiAdjEdge<'a, E>> for DirectedGraph<V,E> where V: Vertex + 'a, E: Edge<VType=V> + 'a {
    type AdjIter = AdjIter<'a, E>;
    type EIter = EIter<'a, E>;
    type VIter = VIter<'a, V>;
    fn add_edge(&mut self, e: E) {
        let ei = Eite(self.m);
        self.m += 1;
        self.g[e.from().id()].push(ei);
        self.vertex_regist(e.from().clone());
        self.vertex_regist(e.to().clone());
        self.es.push(e);
    }
    fn delta(&'a self, v: &V) -> Self::AdjIter {
        AdjIter { iter: self.g[v.id()].iter(), edges: &self.es }
    }
    fn edges(&'a self) -> Self::EIter {
        EIter { i: 0, iter: self.es.iter() }
    }
    fn vertices(&'a self) -> Self::VIter { 
        VIter { iter: self.vs.iter() }
    }
    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(),
            vs: vec![None; n], 
        }
    }

    fn vertex_regist(&mut self, v: V) {
        let i = v.id();
        self.vs[i] = match self.vs[v.id()].take() {
            Some(vv) => {
                assert!(vv.id() == v.id());
                Some(vv)
            }
            None => {
                Some(v)
            }
        }
    }
}

impl<'a, V, E> Directed<'a, V, E, DiAdjEdge<'a, E>> for DirectedGraph<V, E> where V: Vertex + 'a, E: Edge<VType=V> + 'a {}

pub fn scaling_dijkstra<'a, V, E, AE, G, F>(g: &'a G, s: &V, cost: F) -> Properties<NNegW<usize>>
where V: Vertex + 'a, E: Edge<VType=V> + 'a, AE: AdjEdge<V, E>, G: Graph<'a, V, E, AE>, F: Fn(&E) -> NNegW<usize> { 
    type W = NNegW<usize>;
    let n = g.v_size();
    let mut dist = Properties::new(n, &W::zero());
    let mut mw = W::zero();
    for e in g.edges() {
        if mw < cost(e.edge()) { mw = cost(e.edge()); }
    }

    let logw = {
        let mut cnt = 0usize;
        while mw > W::zero() {
            mw = mw >> NNegW::Some(1);
            cnt += 1;
        }
        cnt
    };

    for k in (0..logw+1).rev() {

        for v in g.vertices() {
            dist[&v] = dist[&v] << NNegW::Some(1);
        }

        let mut temp = Properties::new(n, &W::inf());
        temp[s] = W::zero();
        let mut heap = vec![Vec::new(); n];
        heap[0].push(s.clone());

        for d in 0..heap.len() {
            while let Some(v) = heap[d].pop() {
                if temp[&v] < NNegW::Some(d) { continue; }
                for e in g.delta(&v) {
                    let c = (cost(e.edge()) >> NNegW::Some(k)) + dist[e.from()] - dist[e.to()];
                    if temp[e.from()] + c < temp[e.to()] && temp[e.from()] + c < NNegW::Some(heap.len()) {
                        temp[e.to()] = temp[e.from()] + c;
                        heap[d + match c { NNegW::Some(cc) => cc, _ => unreachable!() }].push(e.to().clone());
                    }
                }
            }
        }

        for v in g.vertices() {
            dist[&v] = dist[&v] + temp[&v];
        }
    }

    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,
        }
    }
} 

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 = scaling_dijkstra(&g, &Ver(0, VIP::Yet), |ep| NNegW::Some(ep.2));
    for i in 0..n {
        let ans = res[&Ver(i, VIP::Yet)] + res[&Ver(i, VIP::Used)];
        if let NNegW::Some(d) = ans {
            println!("{}", d);
        }
    }
}
0