結果
| 問題 | No.807 umg tours |
| ユーザー |
 Kutimoti_T
|
| 提出日時 | 2019-04-27 22:26:23 |
| 言語 | Rust (1.77.0 + proconio) |
| 結果 |
AC
|
| 実行時間 | 772 ms / 4,000 ms |
| コード長 | 26,620 bytes |
| コンパイル時間 | 14,775 ms |
| コンパイル使用メモリ | 378,128 KB |
| 実行使用メモリ | 82,048 KB |
| 最終ジャッジ日時 | 2024-05-02 23:48:48 |
| 合計ジャッジ時間 | 24,697 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge4 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 10 ms
12,800 KB |
| testcase_01 | AC | 10 ms
12,928 KB |
| testcase_02 | AC | 10 ms
13,056 KB |
| testcase_03 | AC | 10 ms
13,056 KB |
| testcase_04 | AC | 10 ms
12,928 KB |
| testcase_05 | AC | 9 ms
13,056 KB |
| testcase_06 | AC | 10 ms
13,056 KB |
| testcase_07 | AC | 11 ms
13,056 KB |
| testcase_08 | AC | 9 ms
12,800 KB |
| testcase_09 | AC | 10 ms
12,928 KB |
| testcase_10 | AC | 11 ms
12,800 KB |
| testcase_11 | AC | 376 ms
68,608 KB |
| testcase_12 | AC | 402 ms
51,200 KB |
| testcase_13 | AC | 526 ms
68,992 KB |
| testcase_14 | AC | 212 ms
36,992 KB |
| testcase_15 | AC | 161 ms
31,872 KB |
| testcase_16 | AC | 572 ms
72,448 KB |
| testcase_17 | AC | 772 ms
80,768 KB |
| testcase_18 | AC | 690 ms
80,256 KB |
| testcase_19 | AC | 667 ms
79,232 KB |
| testcase_20 | AC | 397 ms
45,440 KB |
| testcase_21 | AC | 414 ms
46,720 KB |
| testcase_22 | AC | 158 ms
27,648 KB |
| testcase_23 | AC | 120 ms
24,448 KB |
| testcase_24 | AC | 325 ms
64,000 KB |
| testcase_25 | AC | 688 ms
82,048 KB |
ソースコード
pub trait Zero {
fn zero() -> Self;
}
impl Zero for usize { fn zero() -> Self { 0 } }
impl Zero for u64 { fn zero() -> Self { 0 } }
impl Zero for u32 { fn zero() -> Self { 0 } }
impl Zero for u16 { fn zero() -> Self { 0 } }
impl Zero for u8 { fn zero() -> Self { 0 } }
impl Zero for isize { fn zero() -> Self { 0 } }
impl Zero for i64 { fn zero() -> Self { 0 } }
impl Zero for i32 { fn zero() -> Self { 0 } }
impl Zero for i16 { fn zero() -> Self { 0 } }
impl Zero for i8 { fn zero() -> Self { 0 } }
pub trait IsNN {}
impl IsNN for usize {}
impl IsNN for u64 {}
impl IsNN for u32 {}
impl IsNN for u16 {}
impl IsNN for u8 {}
pub trait IsNum: ToNNeg + ToArb { }
impl<N: ToNNeg + ToArb> IsNum for N { }
pub trait ToNNeg {
type Output: Zero + IsNum + IsNN + std::ops::Add<Output=Self::Output> + std::ops::Sub<Output=Self::Output> + std::cmp::Ord + Copy;
fn to_nneg(&self) -> Self::Output;
}
impl ToNNeg for usize {
type Output = usize;
fn to_nneg(&self) -> Self::Output { self.clone() }
}
impl ToNNeg for u64 {
type Output = u64;
fn to_nneg(&self) -> Self::Output { self.clone() }
}
impl ToNNeg for u32 {
type Output = u32;
fn to_nneg(&self) -> Self::Output { self.clone() }
}
impl ToNNeg for u16 {
type Output = u16;
fn to_nneg(&self) -> Self::Output { self.clone() }
}
impl ToNNeg for u8 {
type Output = u8;
fn to_nneg(&self) -> Self::Output { self.clone() }
}
impl ToNNeg for isize {
type Output = usize;
fn to_nneg(&self) -> Self::Output {
match self.clone() {
num if num >= 0 => num as Self::Output,
_ => unreachable!()
}
}
}
impl ToNNeg for i64 {
type Output = u64;
fn to_nneg(&self) -> Self::Output {
match self.clone() {
num if num >= 0 => num as Self::Output,
_ => unreachable!()
}
}
}
impl ToNNeg for i32 {
type Output = u32;
fn to_nneg(&self) -> Self::Output {
match self.clone() {
num if num >= 0 => num as Self::Output,
_ => unreachable!()
}
}
}
impl ToNNeg for i16 {
type Output = u16;
fn to_nneg(&self) -> Self::Output {
match self.clone() {
num if num >= 0 => num as Self::Output,
_ => unreachable!()
}
}
}
impl ToNNeg for i8 {
type Output = u8;
fn to_nneg(&self) -> Self::Output {
match self.clone() {
num if num >= 0 => num as Self::Output,
_ => unreachable!()
}
}
}
pub trait ToArb {
type Output: Zero + IsNum + std::ops::Add<Output=Self::Output> + std::ops::Sub<Output=Self::Output> + std::cmp::Ord + Copy;
fn to_arb(&self) -> Self::Output;
}
impl ToArb for isize {
type Output = isize;
fn to_arb(&self) -> Self::Output { self.clone() }
}
impl ToArb for i64 {
type Output = i64;
fn to_arb(&self) -> Self::Output { self.clone() }
}
impl ToArb for i32 {
type Output = i32;
fn to_arb(&self) -> Self::Output { self.clone() }
}
impl ToArb for i16 {
type Output = i16;
fn to_arb(&self) -> Self::Output { self.clone() }
}
impl ToArb for i8 {
type Output = i8;
fn to_arb(&self) -> Self::Output { self.clone() }
}
impl ToArb for usize {
type Output = isize;
fn to_arb(&self) -> Self::Output {
self.clone() as isize
}
}
impl ToArb for u64 {
type Output = i64;
fn to_arb(&self) -> Self::Output {
self.clone() as i64
}
}
impl ToArb for u32 {
type Output = i32;
fn to_arb(&self) -> Self::Output {
self.clone() as i32
}
}
impl ToArb for u16 {
type Output = i16;
fn to_arb(&self) -> Self::Output {
self.clone() as i16
}
}
impl ToArb for u8 {
type Output = i8;
fn to_arb(&self) -> Self::Output {
self.clone() as i8
}
}
pub trait Integer: Sized + std::ops::Shl<usize, Output=Self> + std::ops::Shr<usize, Output=Self> {}
impl Integer for usize {}
impl Integer for u64 {}
impl Integer for u32 {}
impl Integer for u16 {}
impl Integer for u8 {}
impl Integer for isize {}
impl Integer for i64 {}
impl Integer for i32 {}
impl Integer for i16 {}
impl Integer for i8 {}
/// Trait for properties.
pub trait Property: Copy {}
impl<P> Property for P where P: Copy {}
/// Types implementing `ToNNegWeight` are able to convert to non-negative weights.
/// This trait use the algorithms with potentials (`dijkstra_with_potential`, etc...).
pub trait ToNNegWeight {
/// converting type.
type Output: NNegWeight;
/// convert to non-negative weights.
fn to_nnegw(&self) -> Self::Output;
}
/// Types implementing `ToARbWeight` are able to convert to arbitrary weights.
/// This trait use to reverse from non-negative weight after converting weight.
pub trait ToArbWeight {
/// converting type.
type Output: ArbWeight;
/// convert to non-negative weights.
fn to_arbw(&self) -> Self::Output;
}
/// Trait of arbitrary weights.
/// the arbirary weight has infinity, zero and negative infinity.
pub trait ArbWeight where Self: ToNNegWeight + ToArbWeight + Property + std::ops::Add<Output=Self> + std::cmp::Ord {
fn inf() -> Self;
fn zero() -> Self;
fn neg_inf() -> Self { unreachable!() }
}
/// Trait of non-negative weights.
pub trait NNegWeight where Self: ArbWeight {}
/// Trait of weights of integer.
/// types implementing this use the scaling algorithms.
pub trait IntegerWeight: ArbWeight + std::ops::Shl<usize, Output=Self> + std::ops::Shr<usize, Output=Self> {}
impl<W> IntegerWeight for W where W: ArbWeight + std::ops::Shl<usize, Output=Self> + std::ops::Shr<usize, Output=Self> {}
pub trait SubtractableWeight: ArbWeight + std::ops::Sub<Output=Self> {}
impl<W> SubtractableWeight for W where W: ArbWeight + std::ops::Sub<Output=Self> {}
/// Trait of capacity for maxflow, mcf, and so on.
pub trait Capacity: ArbWeight + IntegerWeight + SubtractableWeight {}
impl<W> Capacity for W where W: ArbWeight + IntegerWeight + SubtractableWeight {}
pub trait Cost<Cap>: ArbWeight + SubtractableWeight + std::ops::Mul<Cap, Output=Self> {}
impl<Co, Cap> Cost<Cap> for Co where Cap: Capacity, Co: ArbWeight + SubtractableWeight + SubtractableWeight + std::ops::Mul<Cap, Output=Self> {}
/// Trait for elements of graph (Vertex, Edge, ...) that have ID (usize).
/// the elements implementing ID are able to use [`graph::kernel::Properties`].
pub trait ID {
/// return id of the element.
fn id(&self) -> usize;
}
/// Implementing ID for usize.
impl ID for usize {
/// return the own value
fn id(&self) -> usize { *self }
}
/// Trait for vertices of graphs.
pub trait Vertex: ID + Eq + Copy { }
impl<V: ID + Eq + Copy> Vertex for V { }
/// Trait for edges of graphs.
pub trait Edge {
/// Vertex type at both ends of edge
type VType: Vertex;
/// Start point of edge
fn from(&self) -> &Self::VType;
/// End point of edge
fn to(&self) -> &Self::VType;
}
/// Implementing Edge for the simple tuple.
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 }
}
/// Implementing Edge for the simple tuple.
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 }
}
/// Trait for adjacency edges of graph.
/// Why do we use [`Edge`] as is? There are 2 reasons.
/// - To give values to the edges to use Properties (AdjEdge has ID).
/// - When using a undirected graph as a directed graph, must swap two ends of edge.
pub trait AdjEdge: ID + Edge {
/// Edge type of raw edge.
type EType: Edge<VType=Self::VType>;
/// return raw edge.
fn edge(&self) -> &Self::EType;
}
/// Trait for adjcency edges on ResidualNetwork.
/// It has reverse edge.
pub trait ResidualEdge: AdjEdge {
fn rev(&self) -> Self;
}
/// Trait of graph.
pub trait Graph<'a> {
/// Type of vertices.
type VType: Vertex + 'a;
/// Type of edges.
type EType: Edge<VType=Self::VType>;
/// Type of adjacency edges.
type AEType: AdjEdge<VType=Self::VType, EType=Self::EType>;
/// Type of iterator for adjacency list.
type AdjIter: std::iter::Iterator<Item=Self::AEType>;
/// Type of iterator for edges list.
type EIter: std::iter::Iterator<Item=Self::AEType>;
/// Type of iterator for vertices list.
type VIter: std::iter::Iterator<Item=&'a Self::VType>;
/// return adjacency list from the vertex v.
fn delta(&'a self, v: &Self::VType) -> Self::AdjIter;
/// return edges list.
fn edges(&'a self) -> Self::EIter;
/// return vertices list.
fn vertices(&'a self) -> Self::VIter;
/// return the number of vertices.
fn v_size(&self) -> usize;
/// return the number of edges.
fn e_size(&self) -> usize;
}
/// Trait of directed graph.
pub trait Directed<'a>: Graph<'a> {}
/// Trait of undirected graph.
/// graphs implementing this hold that the edge `(v, u)` exists for the edge `(u, v)` when the graph
/// use as directed graph
pub trait Undirected<'a>: Graph<'a> {}
/// Trait of bipartite graph.
pub trait Bipartite<'a>: Undirected<'a> {
/// Type of iterator for vertices in one side.
type BVIter: std::iter::Iterator<Item=&'a Self::VType>;
/// return vertices list in left side.
fn left_vertices(&'a self) -> Self::BVIter;
/// return vertices list in right side.
fn right_vertices(&'a self) -> Self::BVIter;
}
/// Trait of residual network
/// `AEType` must be `ResidualEdge`.
pub trait Residual<'a>: Directed<'a> where <Self as Graph<'a>>::AEType: ResidualEdge {}
pub fn generate_func<AE, P, F>(f: F) -> impl Fn(&AE) -> P
where AE: AdjEdge, P: Property, F: Fn(&AE::EType) -> P {
move |ae| f(ae.edge())
}
use std::ops::{ Index, IndexMut };
#[derive(Clone)]
pub struct Properties<W: Clone> {
vec: Vec<W>
}
impl<'a, I: ID, W: Clone> 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: Clone> 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: Clone> Properties<W> {
pub fn new(n: usize, init: &W) -> Self {
Properties {
vec: vec![init.clone(); n],
}
}
pub fn iter(&'a self) -> std::slice::Iter<'a, W> { self.vec.iter() }
}
#[derive(Clone, Copy, PartialEq, Eq)]
pub enum ArbW<W> where W: Zero + IsNum + std::ops::Add<Output=W> + std::cmp::Ord + Copy {
Inf,
Some(W),
NegInf,
}
impl<W> std::ops::Add for ArbW<W> where W: Zero + IsNum + std::ops::Add<Output=W> + std::cmp::Ord + Copy {
type Output = Self;
fn add(self, rhs: Self) -> Self {
match self {
ArbW::Inf => {
match rhs {
ArbW::NegInf => unreachable!(),
_ => ArbW::Inf,
}
}
ArbW::Some(d) => {
match rhs {
ArbW::Inf => ArbW::Inf,
ArbW::Some(d2) => ArbW::Some(d + d2),
ArbW::NegInf => ArbW::NegInf,
}
}
ArbW::NegInf => {
match rhs {
ArbW::Inf => unreachable!(),
_ => ArbW::NegInf,
}
}
}
}
}
impl<W> std::ops::Sub for ArbW<W> where W: Zero + IsNum + 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 {
ArbW::Inf => {
match rhs {
ArbW::Inf => unreachable!(),
_ => ArbW::Inf,
}
}
ArbW::Some(d) => {
match rhs {
ArbW::Inf => ArbW::NegInf,
ArbW::Some(d2) => ArbW::Some(d - d2),
ArbW::NegInf => ArbW::Inf,
}
}
ArbW::NegInf => {
match rhs {
ArbW::NegInf => unreachable!(),
_ => ArbW::NegInf,
}
}
}
}
}
impl<W,X> std::ops::Mul<ArbW<X>> for ArbW<W>
where W: Zero + IsNum + std::ops::Add<Output=W> + std::cmp::Ord + Copy + std::ops::Mul<Output=W>,
X: Zero + IsNum + std::ops::Add<Output=X> + std::cmp::Ord + Copy + Into<W> {
type Output = Self;
fn mul(self, rhs: ArbW<X>) -> Self {
match self {
ArbW::Inf => {
match rhs {
ArbW::NegInf => ArbW::NegInf,
_ => ArbW::Inf,
}
}
ArbW::Some(d) => {
match rhs {
ArbW::Inf => ArbW::Inf,
ArbW::Some(d2) => ArbW::Some(d.mul(d2.into())),
ArbW::NegInf => ArbW::NegInf,
}
}
ArbW::NegInf => {
match rhs {
ArbW::NegInf => ArbW::Inf,
_ => ArbW::NegInf,
}
}
}
}
}
impl<W,X> std::ops::Mul<NNegW<X>> for ArbW<W>
where W: Zero + IsNum + std::ops::Add<Output=W> + std::cmp::Ord + Copy + std::ops::Mul<Output=W>,
X: Zero + IsNum + IsNN + std::ops::Add<Output=X> + std::cmp::Ord + Copy + Into<W> {
type Output = Self;
fn mul(self, rhs: NNegW<X>) -> Self {
match self {
ArbW::Inf => {
ArbW::Inf
}
ArbW::Some(d) => {
match rhs {
NNegW::Inf => ArbW::Inf,
NNegW::Some(d2) => ArbW::Some(d.mul(d2.into())),
}
}
ArbW::NegInf => {
ArbW::NegInf
}
}
}
}
impl<W> std::cmp::PartialOrd for ArbW<W> where W: Zero + IsNum + std::ops::Add<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 ArbW<W> where W: Zero + IsNum + std::ops::Add<Output=W> + std::cmp::Ord + Copy {
fn cmp(&self, rhs: &Self) -> std::cmp::Ordering {
match self {
ArbW::Inf => {
match rhs {
ArbW::Inf => std::cmp::Ordering::Equal,
_ => std::cmp::Ordering::Greater,
}
}
ArbW::Some(d) => {
match rhs {
ArbW::Inf => std::cmp::Ordering::Less,
ArbW::Some(d2) => d.cmp(d2),
ArbW::NegInf => std::cmp::Ordering::Greater,
}
}
ArbW::NegInf => {
match rhs {
ArbW::NegInf => std::cmp::Ordering::Equal,
_ => std::cmp::Ordering::Less,
}
}
}
}
}
impl<W> ToNNegWeight for ArbW<W> where W: Zero + IsNum + std::ops::Add<Output=W> + std::cmp::Ord + Copy {
type Output = NNegW<<W as ToNNeg>::Output>;
fn to_nnegw(&self) -> Self::Output {
match self {
ArbW::Inf => NNegW::Inf,
ArbW::Some(ref num) => NNegW::Some(num.to_nneg()),
ArbW::NegInf => unreachable!(),
}
}
}
impl<W> ToArbWeight for ArbW<W> where W: Zero + IsNum + std::ops::Add<Output=W> + std::cmp::Ord + Copy {
type Output = Self;
fn to_arbw(&self) -> Self::Output {
self.clone()
}
}
impl<W> std::ops::Shl<usize> for ArbW<W>
where W: Zero + IsNum + Integer + std::ops::Add<Output=W> + std::cmp::Ord + Copy {
type Output = Self;
fn shl(self, rhs: usize) -> Self {
match self {
ArbW::Some(d) => ArbW::Some(d.shl(rhs)),
inf => inf,
}
}
}
impl<W> std::ops::Shr<usize> for ArbW<W>
where W: Zero + IsNum + Integer + std::ops::Add<Output=W> + std::cmp::Ord + Copy + std::ops::Shr<usize, Output=W> {
type Output = Self;
fn shr(self, rhs: usize) -> Self {
match self {
ArbW::Some(d) => ArbW::Some(d.shr(rhs)),
inf => inf,
}
}
}
impl<W> ArbWeight for ArbW<W> where W: Zero + IsNum + std::ops::Add<Output=W> + std::cmp::Ord + Copy {
fn inf() -> Self { ArbW::Inf }
fn zero() -> Self { ArbW::Some(W::zero()) }
fn neg_inf() -> Self { ArbW::NegInf }
}
#[derive(Clone, Copy, PartialEq, Eq)]
pub enum NNegW<W> where W: Zero + IsNum + IsNN + std::ops::Add<Output=W> + std::cmp::Ord + Copy {
Inf,
Some(W),
}
impl<W> std::ops::Add for NNegW<W> where W: Zero + IsNum + IsNN + std::ops::Add<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 + IsNum + 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 + IsNum + IsNN + std::ops::Add<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 + IsNum + IsNN + std::ops::Add<Output=W> + std::cmp::Ord + Copy {
fn cmp(&self, rhs: &Self) -> std::cmp::Ordering {
match self {
NNegW::Inf => {
match rhs {
NNegW::Inf => std::cmp::Ordering::Equal,
_ => std::cmp::Ordering::Greater,
}
}
NNegW::Some(d) => {
match rhs {
NNegW::Inf => std::cmp::Ordering::Less,
NNegW::Some(d2) => d.cmp(d2),
}
}
}
}
}
impl<W> IsNN for NNegW<W> where W: Zero + IsNum + IsNN + std::ops::Add<Output=W> + std::cmp::Ord + Copy {}
impl<W> ToNNegWeight for NNegW<W> where W: Zero + IsNum + IsNN + std::ops::Add<Output=W> + std::cmp::Ord + Copy {
type Output = Self;
fn to_nnegw(&self) -> Self::Output {
self.clone()
}
}
impl<W> ToArbWeight for NNegW<W> where W: Zero + IsNum + IsNN + std::ops::Add<Output=W> + std::cmp::Ord + Copy {
type Output = ArbW<<W as ToArb>::Output>;
fn to_arbw(&self) -> Self::Output {
match self {
NNegW::Inf => ArbW::Inf,
NNegW::Some(ref num) => ArbW::Some(num.to_arb())
}
}
}
impl<W> std::ops::Shl<usize> for NNegW<W>
where W: Zero + IsNum + IsNN + Integer + std::ops::Add<Output=W> + std::cmp::Ord + Copy {
type Output = Self;
fn shl(self, rhs: usize) -> Self {
match self {
NNegW::Some(d) => NNegW::Some(d.shl(rhs)),
other => other,
}
}
}
impl<W> std::ops::Shr<usize> for NNegW<W>
where W: Zero + IsNum + IsNN + Integer + std::ops::Add<Output=W> + std::cmp::Ord + Copy {
type Output = Self;
fn shr(self, rhs: usize) -> Self {
match self {
NNegW::Some(d) => NNegW::Some(d.shr(rhs)),
other => other,
}
}
}
impl<W> ArbWeight for NNegW<W> where W: Zero + IsNum + IsNN + std::ops::Add<Output=W> + std::cmp::Ord + Copy {
fn inf() -> Self { NNegW::Inf }
fn zero() -> Self { NNegW::Some(W::zero()) }
}
impl<W> NNegWeight for NNegW<W> where W: Zero + IsNum + IsNN + std::ops::Add<Output=W> + std::cmp::Ord + Copy {}
#[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, E> Edge for DiAdjEdge<'a, E> where E: Edge + 'a {
type VType = E::VType;
fn from(&self) -> &E::VType { self.0.from() }
fn to(&self) -> &E::VType { self.0.to() }
}
impl<'a, E> AdjEdge for DiAdjEdge<'a, E> where E: Edge + 'a {
type EType = E;
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 = &'a V;
fn next(&mut self) -> Option<Self::Item> {
while let Some(v) = self.iter.next() {
if v.is_none() { continue; }
else { return v.as_ref() }
}
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> for DirectedGraph<V,E> where V: Vertex + 'a, E: Edge<VType=V> + 'a {
type VType = V;
type EType = E;
type AEType = DiAdjEdge<'a, E>;
type AdjIter = AdjIter<'a, E>;
type EIter = EIter<'a, E>;
type VIter = VIter<'a, V>;
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)
}
}
}
pub 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);
}
}
impl<'a, V, E> Directed<'a> for DirectedGraph<V, E> where V: Vertex + 'a, E: Edge<VType=V> + 'a {}
use std::collections::BinaryHeap;
use std::cmp::Ordering;
struct DijkstraNode<W: NNegWeight, V: Vertex> {
dist: W,
ver : V,
}
impl<W: NNegWeight, V: Vertex> Ord for DijkstraNode<W, V> {
fn cmp(&self, other: &Self) -> Ordering {
other.dist.cmp(&self.dist)
}
}
impl<W: NNegWeight, V: Vertex> PartialOrd for DijkstraNode<W, V> {
fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
Some(other.dist.cmp(&self.dist))
}
}
impl<W: NNegWeight, V: Vertex> PartialEq for DijkstraNode<W, V> {
fn eq(&self, other: &Self) -> bool {
self.dist == other.dist
}
}
impl<W: NNegWeight, V: Vertex> Eq for DijkstraNode<W, V> { }
pub fn dijkstra<'a, G, W, F>(g: &'a G, s: &G::VType, cost: F) -> Properties<W>
where G: Graph<'a>, W: NNegWeight, F: Fn(&G::AEType) -> W {
let n = g.v_size();
let mut dist = Properties::new(n, &W::inf());
dist[s] = W::zero();
let mut heap = BinaryHeap::new();
heap.push(DijkstraNode { dist: dist[s], ver: s.clone() });
while let Some(DijkstraNode { dist: d, ver: ref v}) = heap.pop() {
if dist[v] < d { continue }
for ref e in g.delta(v) {
if dist[e.from()] + cost(e) < dist[e.to()] {
dist[e.to()] = dist[e.from()] + cost(e);
heap.push(DijkstraNode{ dist: dist[e.to()], ver: e.to().clone() })
}
}
}
dist
}
#[derive(Clone, PartialEq, Eq, Copy)]
enum VIP {
Yet,
Used,
}
#[derive(Clone, PartialEq, Eq, Copy)]
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 = dijkstra(&g, &Ver(0, VIP::Yet), |ep| NNegW::Some(ep.edge().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);
}
}
}