結果
| 問題 |
No.807 umg tours
|
| コンテスト | |
| ユーザー |
 niuez
|
| 提出日時 | 2019-03-29 16:33:30 |
| 言語 | Rust (1.83.0 + proconio) |
| 結果 |
AC
|
| 実行時間 | 588 ms / 4,000 ms |
| コード長 | 6,332 bytes |
| コンパイル時間 | 15,814 ms |
| コンパイル使用メモリ | 378,740 KB |
| 実行使用メモリ | 88,448 KB |
| 最終ジャッジ日時 | 2024-11-23 19:21:59 |
| 合計ジャッジ時間 | 20,744 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 26 |
ソースコード
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());
}
}