結果
| 問題 | No.1301 Strange Graph Shortest Path |
| ユーザー |
 cotton_fn_
|
| 提出日時 | 2020-11-27 23:30:43 |
| 言語 | Rust (1.77.0 + proconio) |
| 結果 |
AC
|
| 実行時間 | 269 ms / 3,000 ms |
| コード長 | 8,781 bytes |
| コンパイル時間 | 13,698 ms |
| コンパイル使用メモリ | 397,472 KB |
| 実行使用メモリ | 39,940 KB |
| 最終ジャッジ日時 | 2024-09-13 01:08:01 |
| 合計ジャッジ時間 | 21,115 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge5 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 1 ms
6,816 KB |
| testcase_01 | AC | 2 ms
6,812 KB |
| testcase_02 | AC | 269 ms
39,424 KB |
| testcase_03 | AC | 201 ms
35,584 KB |
| testcase_04 | AC | 205 ms
38,272 KB |
| testcase_05 | AC | 122 ms
39,936 KB |
| testcase_06 | AC | 159 ms
35,328 KB |
| testcase_07 | AC | 149 ms
37,120 KB |
| testcase_08 | AC | 114 ms
36,096 KB |
| testcase_09 | AC | 156 ms
33,664 KB |
| testcase_10 | AC | 118 ms
35,456 KB |
| testcase_11 | AC | 166 ms
36,480 KB |
| testcase_12 | AC | 171 ms
36,480 KB |
| testcase_13 | AC | 147 ms
39,808 KB |
| testcase_14 | AC | 150 ms
33,536 KB |
| testcase_15 | AC | 148 ms
34,816 KB |
| testcase_16 | AC | 189 ms
38,144 KB |
| testcase_17 | AC | 160 ms
39,680 KB |
| testcase_18 | AC | 136 ms
36,480 KB |
| testcase_19 | AC | 168 ms
35,712 KB |
| testcase_20 | AC | 170 ms
34,688 KB |
| testcase_21 | AC | 151 ms
38,400 KB |
| testcase_22 | AC | 167 ms
35,712 KB |
| testcase_23 | AC | 146 ms
39,552 KB |
| testcase_24 | AC | 153 ms
35,328 KB |
| testcase_25 | AC | 175 ms
38,144 KB |
| testcase_26 | AC | 155 ms
36,608 KB |
| testcase_27 | AC | 161 ms
36,736 KB |
| testcase_28 | AC | 128 ms
39,552 KB |
| testcase_29 | AC | 195 ms
37,760 KB |
| testcase_30 | AC | 173 ms
37,888 KB |
| testcase_31 | AC | 183 ms
37,632 KB |
| testcase_32 | AC | 1 ms
6,944 KB |
| testcase_33 | AC | 76 ms
31,232 KB |
| testcase_34 | AC | 181 ms
39,940 KB |
ソースコード
#![allow(unused_imports, unused_macros)]
use kyoproio::*;
use std::{
collections::*,
io::{self, prelude::*},
iter,
mem::{replace, swap},
};
fn run<I: Input, O: Write>(mut kin: I, mut out: O) {
macro_rules! output { ($($args:expr),+) => { write!(&mut out, $($args),+).unwrap(); }; }
macro_rules! outputln {
($($args:expr),+) => { output!($($args),+); outputln!(); };
() => { output!("\n"); if cfg!(debug_assertions) { out.flush().unwrap(); } }
}
let (n, m): (usize, usize) = kin.input();
let mut g = MinCostFlow::new(n + 1);
for (u, v, c, d) in kin.iter::<(usize, usize, i64, i64)>().take(m) {
g.add_edge(u, v, 1, c);
g.add_edge(u, v, 1, d);
g.add_edge(v, u, 1, c);
g.add_edge(v, u, 1, d);
}
let (f, ans) = g.run(1, n, 2);
assert_eq!(f, 2);
outputln!("{}", ans);
}
pub struct MinCostFlow {
g: Vec<Vec<Edge>>,
}
#[derive(Clone, Copy)]
struct Edge {
v: usize,
rev: usize,
cap: i32,
cost: i64,
}
impl MinCostFlow {
pub fn new(n: usize) -> Self {
Self {
g: vec![Vec::new(); n],
}
}
pub fn add_edge(&mut self, u: usize, v: usize, cap: i32, cost: i64) {
let rev_u = self.g[v].len();
let rev_v = self.g[u].len();
self.g[u].push(Edge {
v,
rev: rev_u,
cap,
cost,
});
self.g[v].push(Edge {
v: u,
rev: rev_v,
cap: 0,
cost: -cost,
})
}
pub fn run(&mut self, s: usize, t: usize, limit: i32) -> (i32, i64) {
use std::cmp::Reverse;
let n = self.g.len();
let mut flow = 0;
let mut cost = 0;
let mut p = vec![0; n];
let mut dist = vec![0; n];
let mut que = std::collections::BinaryHeap::new();
let mut prev = vec![(0, 0); n];
while flow < limit {
dist.clear();
dist.resize(n, i64::max_value());
dist[s] = 0;
que.push((Reverse(0), s));
prev[t].0 = !0;
while let Some((Reverse(d), u)) = que.pop() {
if dist[u] < d {
continue;
}
for (i, e) in self.g[u].iter().enumerate() {
let dd = d + e.cost - p[e.v] + p[u];
if e.cap > 0 && dd < dist[e.v] {
dist[e.v] = dd;
que.push((Reverse(dd), e.v));
prev[e.v] = (u, i);
}
}
}
if prev[t].0 == !0 {
break;
}
for u in 0..n {
if dist[u] != i64::max_value() {
p[u] += dist[u];
}
}
let mut v = t;
let mut add = limit - flow;
while v != s {
let (u, i) = prev[v];
add = add.min(self.g[u][i].cap);
v = u;
}
flow += add;
let mut v = t;
while v != s {
let (u, i) = prev[v];
let e = &mut self.g[u][i];
cost += e.cost * add as i64;
e.cap -= add;
let rev = e.rev;
self.g[v][rev].cap += add;
v = u;
}
}
(flow, cost)
}
}
// -----------------------------------------------------------------------------
fn main() -> io::Result<()> {
std::thread::Builder::new()
.stack_size(64 * 1024 * 1024)
.spawn(|| {
run(
KInput::new(io::stdin()),
io::BufWriter::new(io::stdout().lock()),
)
})?
.join()
.unwrap();
Ok(())
}
// -----------------------------------------------------------------------------
pub mod kyoproio {
use std::{io::prelude::*, mem};
pub trait Input {
fn bytes(&mut self) -> &[u8];
fn str(&mut self) -> &str {
std::str::from_utf8(self.bytes()).unwrap()
}
fn input<T: InputParse>(&mut self) -> T {
T::input(self)
}
fn iter<T: InputParse>(&mut self) -> Iter<T, Self> {
Iter(self, std::marker::PhantomData)
}
fn seq<T: InputParse, B: std::iter::FromIterator<T>>(&mut self, n: usize) -> B {
self.iter().take(n).collect()
}
}
pub struct KInput<R> {
src: R,
buf: Vec<u8>,
pos: usize,
len: usize,
}
impl<R: Read> KInput<R> {
pub fn new(src: R) -> Self {
Self {
src,
buf: vec![0; 1 << 16],
pos: 0,
len: 0,
}
}
}
impl<R: Read> Input for KInput<R> {
fn bytes(&mut self) -> &[u8] {
loop {
while let Some(delim) = self.buf[self.pos..self.len]
.iter()
.position(|b| b.is_ascii_whitespace())
{
let p = self.pos;
self.pos += delim + 1;
if delim > 0 {
return &self.buf[p..p + delim];
}
}
if self.read() == 0 {
return &self.buf[mem::replace(&mut self.pos, self.len)..self.len];
}
}
}
}
impl<R: Read> KInput<R> {
fn read(&mut self) -> usize {
if self.pos > 0 {
self.buf.copy_within(self.pos..self.len, 0);
self.len -= self.pos;
self.pos = 0;
} else if self.len >= self.buf.len() {
self.buf.resize(2 * self.buf.len(), 0);
}
let read = self.src.read(&mut self.buf[self.len..]).unwrap();
self.len += read;
read
}
}
pub struct Iter<'a, T, I: ?Sized>(&'a mut I, std::marker::PhantomData<*const T>);
impl<'a, T: InputParse, I: Input + ?Sized> Iterator for Iter<'a, T, I> {
type Item = T;
fn next(&mut self) -> Option<T> {
Some(self.0.input())
}
fn size_hint(&self) -> (usize, Option<usize>) {
(!0, None)
}
}
pub trait InputParse: Sized {
fn input<I: Input + ?Sized>(src: &mut I) -> Self;
}
impl InputParse for Vec<u8> {
fn input<I: Input + ?Sized>(src: &mut I) -> Self {
src.bytes().to_owned()
}
}
macro_rules! from_str_impl {
{ $($T:ty)* } => {
$(impl InputParse for $T {
fn input<I: Input + ?Sized>(src: &mut I) -> Self {
src.str().parse::<$T>().unwrap()
}
})*
}
}
from_str_impl! { String char bool f32 f64 }
macro_rules! parse_int_impl {
{ $($I:ty: $U:ty)* } => {
$(impl InputParse for $I {
fn input<I: Input + ?Sized>(src: &mut I) -> Self {
let f = |s: &[u8]| s.iter().fold(0, |x, b| 10 * x + (b & 0xf) as $I);
let s = src.bytes();
if let Some((&b'-', t)) = s.split_first() { -f(t) } else { f(s) }
}
}
impl InputParse for $U {
fn input<I: Input + ?Sized>(src: &mut I) -> Self {
src.bytes().iter().fold(0, |x, b| 10 * x + (b & 0xf) as $U)
}
})*
};
}
parse_int_impl! { isize:usize i8:u8 i16:u16 i32:u32 i64:u64 i128:u128 }
macro_rules! tuple_impl {
($H:ident $($T:ident)*) => {
impl<$H: InputParse, $($T: InputParse),*> InputParse for ($H, $($T),*) {
fn input<I: Input + ?Sized>(src: &mut I) -> Self {
($H::input(src), $($T::input(src)),*)
}
}
tuple_impl!($($T)*);
};
() => {}
}
tuple_impl!(A B C D E F G);
macro_rules! array_impl {
{ $($N:literal)* } => {
$(impl<T: InputParse> InputParse for [T; $N] {
fn input<I: Input + ?Sized>(src: &mut I) -> Self {
let mut arr = mem::MaybeUninit::uninit();
unsafe {
let ptr = arr.as_mut_ptr() as *mut T;
for i in 0..$N {
ptr.add(i).write(src.input());
}
arr.assume_init()
}
}
})*
};
}
array_impl! { 1 2 3 4 5 6 7 8 }
#[macro_export]
macro_rules! kdbg {
($($v:expr),*) => {
if cfg!(debug_assertions) { dbg!($($v),*) } else { ($($v),*) }
}
}
}