結果
| 問題 |
No.1069 電柱 / Pole (Hard)
|
| コンテスト | |
| ユーザー |
 Haar
|
| 提出日時 | 2024-07-04 19:12:18 |
| 言語 | Rust (1.83.0 + proconio) |
| 結果 |
AC
|
| 実行時間 | 113 ms / 2,000 ms |
| コード長 | 17,252 bytes |
| コンパイル時間 | 17,512 ms |
| コンパイル使用メモリ | 378,212 KB |
| 実行使用メモリ | 16,128 KB |
| 最終ジャッジ日時 | 2024-07-04 19:12:41 |
| 合計ジャッジ時間 | 20,926 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 4 |
| other | AC * 79 |
コンパイルメッセージ
warning: unused import: `utils::join_str::*` --> src/main.rs:11:9 | 11 | utils::join_str::*, | ^^^^^^^^^^^^^^^^^^ | = note: `#[warn(unused_imports)]` on by default
ソースコード
// Bundled at 2024/07/04 19:11:45 +09:00
// Author: Haar
pub mod main {
use super::*;
use haar_lib::{
get,
graph::{yen::*, *},
input,
utils::fastio::*,
utils::join_str::*,
utils::total_f64::*,
};
#[allow(unused_imports)]
use std::cell::RefCell;
#[allow(unused_imports)]
use std::collections::{BTreeMap, BTreeSet, BinaryHeap, HashMap, HashSet};
#[allow(unused_imports)]
use std::io::Write;
#[allow(unused_imports)]
use std::rc::Rc;
#[derive(Clone, Default)]
pub struct Problem {}
impl Problem {
pub fn main(&mut self) -> Result<(), Box<dyn std::error::Error>> {
let mut io = FastIO::new();
input!(io >> n: usize, m: usize, k: usize);
let x = io.read_usize() - 1;
let y = io.read_usize() - 1;
let mut ps = vec![];
let mut qs = vec![];
for _ in 0..n {
ps.push(io.read_i64());
qs.push(io.read_i64());
}
let mut g = Graph::<Undirected, _>::new(n);
for _ in 0..m {
let p = io.read_usize() - 1;
let q = io.read_usize() - 1;
let dx = (ps[p] - ps[q]) as f64;
let dy = (qs[p] - qs[q]) as f64;
let l = (dx * dx + dy * dy).sqrt();
g.add(Edge::new(p, q, Totalf64(l), ()));
}
let ans = yen_algorithm(&g, x, y, k);
for a in ans {
if let Some((Totalf64(a), _)) = a {
io.writeln(a);
} else {
io.writeln(-1);
}
}
Ok(())
}
}
}
fn main() {
main::Problem::default().main().unwrap();
}
use crate as haar_lib;
pub mod graph {
pub mod yen {
use crate::trait_alias;
use crate::{graph::*, traits::one_zero::Zero};
use std::ops::{Add, AddAssign};
use std::{cmp::Reverse, collections::BinaryHeap};
trait_alias!(
Elem,
Zero<Output = Self> + Add<Output = Self> + AddAssign + Ord + Eq + Copy
);
type Path = Vec<usize>;
fn shortest_path<D: Direction, T: Elem, E: EdgeTrait<Weight = T>>(
g: &Graph<D, E>,
from: usize,
t: usize,
usable: &Vec<bool>,
valid: &Vec<Vec<bool>>,
) -> Option<(T, Path)> {
let n = g.len();
let mut visited = vec![false; n];
let mut dist = vec![None; n];
let mut restore = vec![(0, 0); n];
let mut pq = BinaryHeap::<Reverse<(T, usize)>>::new();
dist[from] = Some(T::zero());
pq.push(Reverse((T::zero(), from)));
while let Some(Reverse((d, i))) = pq.pop() {
if visited[i] {
continue;
}
visited[i] = true;
for (k, e) in g.edges[i].iter().enumerate() {
if !valid[i][k] || !usable[e.to()] {
continue;
}
if dist[e.to()].is_none() || dist[e.to()].unwrap() > d + e.weight() {
dist[e.to()] = Some(d + e.weight());
restore[e.to()] = (i, k);
if !visited[e.to()] {
pq.push(Reverse((dist[e.to()].unwrap(), e.to())));
}
}
}
}
if let Some(d) = dist[t] {
let mut p = vec![];
let mut cur = t;
while cur != from {
let (i, j) = restore[cur];
p.push(j);
cur = i;
}
p.reverse();
Some((d, p))
} else {
None
}
}
pub fn yen_algorithm<D: Direction, T: Elem, E: EdgeTrait<Weight = T>>(
g: &Graph<D, E>,
s: usize,
t: usize,
k: usize,
) -> Vec<Option<(T, Path)>> {
let n = g.len();
let mut valid = vec![vec![]; n];
let mut result: Vec<Option<(T, Path)>> = vec![None; k];
let mut stock = BinaryHeap::<Reverse<(T, Path)>>::new();
for i in 0..n {
valid[i] = vec![true; g.edges[i].len()];
}
for i in 0..k {
if i == 0 {
let usable = vec![true; n];
if let Some((c, p)) = shortest_path(g, s, t, &usable, &valid) {
stock.push(Reverse((c, p)));
}
} else {
let mut prev_path = vec![];
let mut cur = s;
for &u in &result[i - 1].as_ref().unwrap().1 {
prev_path.push(cur);
cur = g.edges[cur][u].to();
}
prev_path.push(t);
let mut check = vec![true; i];
let mut usable = vec![true; n];
for k in 0..prev_path.len() - 1 {
let u = prev_path[k];
for j in 0..i {
if check[j] {
valid[prev_path[k]][result[j].as_ref().unwrap().1[k]] = false;
}
}
if let Some((mut c, p)) = shortest_path(g, u, t, &usable, &valid) {
let mut temp = vec![];
for j in 0..k {
let v = result[i - 1].as_ref().unwrap().1[j];
c += g.edges[prev_path[j]][v].weight();
temp.push(v);
}
temp.extend(p.into_iter());
stock.push(Reverse((c, temp)));
}
usable[u] = false;
for j in 0..i {
if check[j] {
valid[prev_path[k]][result[j].as_ref().unwrap().1[k]] = true;
}
}
for j in 0..i {
if check[j] {
if prev_path[k + 1]
!= g.edges[prev_path[k]][result[j].as_ref().unwrap().1[k]].to()
{
check[j] = false;
}
}
}
}
}
if stock.is_empty() {
break;
}
result[i] = stock.pop().map(|Reverse((c, p))| (c, p));
while stock.peek().map(|Reverse((c, p))| (*c, p.clone())) == result[i] {
stock.pop();
}
}
result
}
}
use std::marker::PhantomData;
pub trait EdgeTrait {
type Weight;
fn from(&self) -> usize;
fn to(&self) -> usize;
fn weight(&self) -> Self::Weight;
fn rev(self) -> Self;
}
#[derive(Debug, Clone)]
pub struct Edge<T, I> {
pub from: usize,
pub to: usize,
pub weight: T,
pub index: I,
}
impl<T, I> Edge<T, I> {
pub fn new(from: usize, to: usize, weight: T, index: I) -> Self {
Self {
from,
to,
weight,
index,
}
}
}
impl<T: Clone, I> EdgeTrait for Edge<T, I> {
type Weight = T;
#[inline]
fn from(&self) -> usize {
self.from
}
#[inline]
fn to(&self) -> usize {
self.to
}
#[inline]
fn weight(&self) -> Self::Weight {
self.weight.clone()
}
fn rev(mut self) -> Self {
std::mem::swap(&mut self.from, &mut self.to);
self
}
}
pub trait Direction {}
#[derive(Debug, Clone)]
pub struct Directed;
#[derive(Debug, Clone)]
pub struct Undirected;
impl Direction for Directed {}
impl Direction for Undirected {}
#[derive(Debug, Clone)]
pub struct Graph<D, E> {
pub edges: Vec<Vec<E>>,
__phantom: PhantomData<D>,
}
impl<D: Direction, E: EdgeTrait + Clone> Graph<D, E> {
pub fn new(size: usize) -> Self {
Graph {
edges: vec![vec![]; size],
__phantom: PhantomData,
}
}
}
impl<E: EdgeTrait + Clone> Graph<Directed, E> {
pub fn add(&mut self, e: E) {
self.edges[e.from()].push(e);
}
pub fn extend(&mut self, edges: impl IntoIterator<Item = E>) {
edges.into_iter().for_each(|e| self.add(e));
}
}
impl<E: EdgeTrait + Clone> Graph<Undirected, E> {
pub fn add(&mut self, e: E) {
self.edges[e.from()].push(e.clone());
self.edges[e.to()].push(e.rev());
}
pub fn extend(&mut self, edges: impl IntoIterator<Item = E>) {
edges.into_iter().for_each(|e| self.add(e));
}
}
impl<D, E> Graph<D, E> {
pub fn len(&self) -> usize {
self.edges.len()
}
pub fn is_empty(&self) -> bool {
self.edges.is_empty()
}
}
}
pub mod macros {
pub mod io {
#[macro_export]
macro_rules! get {
( $in:ident, [$a:tt $(as $to:ty)*; $num:expr] ) => {
{
let n = $num;
(0 .. n).map(|_| get!($in, $a $(as $to)*)).collect::<Vec<_>>()
}
};
( $in:ident, ($($type:tt $(as $to:ty)*),*) ) => {
($(get!($in, $type $(as $to)*)),*)
};
( $in:ident, i8 ) => { $in.read_i64() as i8 };
( $in:ident, i16 ) => { $in.read_i64() as i16 };
( $in:ident, i32 ) => { $in.read_i64() as i32 };
( $in:ident, i64 ) => { $in.read_i64() };
( $in:ident, isize ) => { $in.read_i64() as isize };
( $in:ident, u8 ) => { $in.read_u64() as u8 };
( $in:ident, u16 ) => { $in.read_u64() as u16 };
( $in:ident, u32 ) => { $in.read_u64() as u32 };
( $in:ident, u64 ) => { $in.read_u64() };
( $in:ident, usize ) => { $in.read_u64() as usize };
( $in:ident, [char] ) => { $in.read_chars() };
( $in:ident, $from:tt as $to:ty ) => { <$to>::from(get!($in, $from)) };
}
#[macro_export]
macro_rules! input {
( @inner $in:ident, mut $name:ident : $type:tt ) => {
let mut $name = get!($in, $type);
};
( @inner $in:ident, mut $name:ident : $type:tt as $to:ty ) => {
let mut $name = get!($in, $type as $to);
};
( @inner $in:ident, $name:ident : $type:tt ) => {
let $name = get!($in, $type);
};
( @inner $in:ident, $name:ident : $type:tt as $to:ty ) => {
let $name = get!($in, $type as $to);
};
( $in:ident >> $($($names:ident)* : $type:tt $(as $to:ty)*),* ) => {
$(input!(@inner $in, $($names)* : $type $(as $to)*);)*
}
}
}
pub mod trait_alias {
#[macro_export]
macro_rules! trait_alias {
($name:ident, $($t:tt)+) => {
pub trait $name : $($t)+ {}
impl<T: $($t)+> $name for T {}
}
}
}
}
pub mod traits {
pub mod one_zero {
#[doc = " 加算についての単位元をもつ"]
pub trait Zero {
type Output;
fn zero() -> Self::Output;
}
#[doc = " 乗算についての単位元をもつ"]
pub trait One {
type Output;
fn one() -> Self::Output;
}
macro_rules! impl_one_zero {
($($t:ty),*) => {
$(
impl Zero for $t {
type Output = $t;
fn zero() -> Self::Output { 0 as $t }
}
impl One for $t {
type Output = $t;
fn one() -> Self::Output { 1 as $t }
}
)*
}
}
impl_one_zero!(u8, u16, u32, u64, u128, usize, i8, i16, i32, i64, i128, isize, f32, f64);
}
}
pub mod utils {
pub mod fastio {
use std::fmt::Display;
use std::io::{Read, Write};
pub struct FastIO {
in_bytes: Vec<u8>,
in_cur: usize,
out_buf: std::io::BufWriter<std::io::Stdout>,
}
impl FastIO {
pub fn new() -> Self {
let mut s = vec![];
std::io::stdin().read_to_end(&mut s).unwrap();
let cout = std::io::stdout();
Self {
in_bytes: s,
in_cur: 0,
out_buf: std::io::BufWriter::new(cout),
}
}
#[inline]
pub fn getc(&mut self) -> Option<u8> {
if self.in_cur < self.in_bytes.len() {
self.in_cur += 1;
Some(self.in_bytes[self.in_cur])
} else {
None
}
}
#[inline]
pub fn peek(&self) -> Option<u8> {
if self.in_cur < self.in_bytes.len() {
Some(self.in_bytes[self.in_cur])
} else {
None
}
}
#[inline]
pub fn skip(&mut self) {
while self.peek().map_or(false, |c| c.is_ascii_whitespace()) {
self.in_cur += 1;
}
}
pub fn read_u64(&mut self) -> u64 {
self.skip();
let mut ret: u64 = 0;
while self.peek().map_or(false, |c| c.is_ascii_digit()) {
ret = ret * 10 + (self.in_bytes[self.in_cur] - b'0') as u64;
self.in_cur += 1;
}
ret
}
pub fn read_u32(&mut self) -> u32 {
self.read_u64() as u32
}
pub fn read_usize(&mut self) -> usize {
self.read_u64() as usize
}
pub fn read_i64(&mut self) -> i64 {
self.skip();
let mut ret: i64 = 0;
let minus = if self.peek() == Some(b'-') {
self.in_cur += 1;
true
} else {
false
};
while self.peek().map_or(false, |c| c.is_ascii_digit()) {
ret = ret * 10 + (self.in_bytes[self.in_cur] - b'0') as i64;
self.in_cur += 1;
}
if minus {
ret = -ret;
}
ret
}
pub fn read_i32(&mut self) -> i32 {
self.read_i64() as i32
}
pub fn read_isize(&mut self) -> isize {
self.read_i64() as isize
}
pub fn read_chars(&mut self) -> Vec<char> {
self.skip();
let mut ret = vec![];
while self.peek().map_or(false, |c| c.is_ascii_graphic()) {
ret.push(self.in_bytes[self.in_cur] as char);
self.in_cur += 1;
}
ret
}
pub fn write<T: Display>(&mut self, s: T) {
self.out_buf.write_all(format!("{}", s).as_bytes()).unwrap();
}
pub fn writeln<T: Display>(&mut self, s: T) {
self.write(s);
self.out_buf.write_all(&[b'\n']).unwrap();
}
}
impl Drop for FastIO {
fn drop(&mut self) {
self.out_buf.flush().unwrap();
}
}
}
pub mod join_str {
pub trait JoinStr {
fn join_str(self, _: &str) -> String;
}
impl<T, I> JoinStr for I
where
T: ToString,
I: Iterator<Item = T>,
{
fn join_str(self, s: &str) -> String {
self.map(|x| x.to_string()).collect::<Vec<_>>().join(s)
}
}
}
pub mod total_f64 {
use crate::traits::one_zero::*;
use std::{
cmp::Ordering,
ops::{Add, AddAssign},
};
#[derive(Clone, Copy, Debug, PartialOrd, PartialEq)]
pub struct Totalf64(pub f64);
impl Eq for Totalf64 {}
impl Ord for Totalf64 {
fn cmp(&self, other: &Self) -> Ordering {
self.0.partial_cmp(&other.0).unwrap()
}
}
impl Add for Totalf64 {
type Output = Self;
fn add(self, rhs: Self) -> Self::Output {
Self(self.0 + rhs.0)
}
}
impl AddAssign for Totalf64 {
fn add_assign(&mut self, rhs: Self) {
self.0 += rhs.0;
}
}
impl Zero for Totalf64 {
type Output = Self;
fn zero() -> Self::Output {
Totalf64(0.0)
}
}
}
}