結果
| 問題 | No.807 umg tours |
| ユーザー |
 Kutimoti_T
|
| 提出日時 | 2019-04-29 09:49:46 |
| 言語 | Rust (1.77.0 + proconio) |
| 結果 |
AC
|
| 実行時間 | 699 ms / 4,000 ms |
| コード長 | 28,122 bytes |
| コンパイル時間 | 14,231 ms |
| コンパイル使用メモリ | 377,668 KB |
| 実行使用メモリ | 85,852 KB |
| 最終ジャッジ日時 | 2024-05-02 23:51:10 |
| 合計ジャッジ時間 | 22,585 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge4 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 10 ms
12,928 KB |
| testcase_01 | AC | 10 ms
13,056 KB |
| testcase_02 | AC | 10 ms
12,928 KB |
| testcase_03 | AC | 11 ms
13,184 KB |
| testcase_04 | AC | 10 ms
12,928 KB |
| testcase_05 | AC | 10 ms
13,184 KB |
| testcase_06 | AC | 11 ms
13,056 KB |
| testcase_07 | AC | 10 ms
13,056 KB |
| testcase_08 | AC | 9 ms
12,928 KB |
| testcase_09 | AC | 10 ms
12,800 KB |
| testcase_10 | AC | 10 ms
12,928 KB |
| testcase_11 | AC | 358 ms
69,792 KB |
| testcase_12 | AC | 377 ms
53,208 KB |
| testcase_13 | AC | 505 ms
70,620 KB |
| testcase_14 | AC | 202 ms
38,600 KB |
| testcase_15 | AC | 172 ms
32,868 KB |
| testcase_16 | AC | 533 ms
75,140 KB |
| testcase_17 | AC | 684 ms
85,852 KB |
| testcase_18 | AC | 677 ms
83,156 KB |
| testcase_19 | AC | 673 ms
81,652 KB |
| testcase_20 | AC | 420 ms
46,488 KB |
| testcase_21 | AC | 437 ms
47,704 KB |
| testcase_22 | AC | 184 ms
28,228 KB |
| testcase_23 | AC | 144 ms
24,704 KB |
| testcase_24 | AC | 309 ms
65,916 KB |
| testcase_25 | AC | 699 ms
84,728 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 {}
pub fn bsr64(x: u64) -> usize {
if x == 0 { 0 }
else {
let mut t = 16usize;
for i in (0..=4).rev() {
if x & !((1u64 << t) - 1) != 0 { t += 1usize << i; }
else { t -= 1usize << i; }
}
if x & !((1u64 << t) - 1) != 0 { t += 1; }
t
}
}
pub struct RadixHeap64<T> {
v: Vec<Vec<(u64, T)>>,
last: u64,
size: usize,
}
impl<T> RadixHeap64<T> {
pub fn new() -> Self {
let mut temp = Vec::new();
for _ in 0..65 { temp.push(Vec::new()); }
RadixHeap64 { v: temp, last: 0, size: 0 }
}
pub fn pop(&mut self) -> Option<(u64, T)> {
if self.is_empty() {
None
}
else {
self.size -= 1;
if self.v[0].is_empty() {
let mut i = 1;
while self.v[i].is_empty() { i += 1; }
self.last = u64::max_value();
for d in self.v[i].iter() {
self.last = std::cmp::min(self.last, d.0.clone());
}
for d in std::mem::replace(&mut self.v[i], Vec::new()) {
self.v[bsr64(self.last ^ d.0)].push(d);
}
}
self.v[0].pop()
}
}
pub fn push(&mut self, x: (u64, T)) {
assert!(self.last <= x.0);
self.size += 1;
self.v[bsr64(self.last ^ x.0)].push(x);
}
pub fn is_empty(&self) -> bool { self.size == 0 }
pub fn size(&self) -> usize { self.size }
}
pub fn dijkstra_with_radix64<'a, G, F>(g: &'a G, s: &G::VType, cost: F) -> Properties<NNegW<u64>>
where G: Graph<'a>, F: Fn(&G::AEType) -> NNegW<u64> {
type W = NNegW<u64>;
let n = g.v_size();
let mut dist = Properties::new(n, &W::inf());
dist[s] = W::zero();
let mut heap = RadixHeap64::new();
heap.push((match dist[s] { NNegW::Some(raw) => raw, _ => unreachable!()}, s.clone()));
while let Some((raw, ref v)) = heap.pop() {
if dist[v] < NNegW::Some(raw) { 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((match dist[e.to()] { NNegW::Some(raw) => raw, _ => unreachable!()}, e.to().clone()));
}
}
}
dist
}
#[test]
fn dijkstra_test() {
use graph::graph::DirectedGraph;
use graph::property::NNegW;
let mut g = DirectedGraph::new(4);
g.add_edge((0usize, 1usize, 1u64));
g.add_edge((0, 2, 4));
g.add_edge((2, 0, 1));
g.add_edge((1, 2, 2));
g.add_edge((3, 1, 1));
g.add_edge((3, 2, 5));
let dist = dijkstra_with_radix64(&g, &1, |e| NNegW::Some(e.edge().2));
assert!(dist[&0] == NNegW::Some(3));
assert!(dist[&1] == NNegW::Some(0));
assert!(dist[&2] == NNegW::Some(2));
assert!(dist[&3] == NNegW::Inf);
}
#[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] as u64);
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_with_radix64(&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);
}
}
}