結果
| 問題 |
No.1069 電柱 / Pole (Hard)
|
| ユーザー |
 Haar
|
| 提出日時 | 2025-04-06 15:46:26 |
| 言語 | Rust (1.83.0 + proconio) |
| 結果 |
AC
|
| 実行時間 | 127 ms / 2,000 ms |
| コード長 | 22,076 bytes |
| コンパイル時間 | 18,602 ms |
| コンパイル使用メモリ | 400,496 KB |
| 実行使用メモリ | 16,256 KB |
| 最終ジャッジ日時 | 2025-04-06 15:46:55 |
| 合計ジャッジ時間 | 21,792 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 4 |
| other | AC * 79 |
ソースコード
// Bundled at 2025/04/06 15:45:48 +09:00
// Author: Haar
pub mod main {
use super::*;
#[allow(unused_imports)]
use haar_lib::{get, input, io::fastio::*, iter::join_str::*};
#[allow(unused_imports)]
use std::cell::{Cell, RefCell};
#[allow(unused_imports)]
use std::cmp::{max, min, Reverse};
#[allow(unused_imports)]
use std::collections::{BTreeMap, BTreeSet, BinaryHeap, HashMap, HashSet, VecDeque};
#[allow(unused_imports)]
use std::io::Write;
#[allow(unused_imports)]
use std::mem::swap;
#[allow(unused_imports)]
use std::rc::Rc;
#[derive(Clone, Default)]
pub struct Problem {}
use haar_lib::graph::{yen::*, *};
use haar_lib::num::total_f64::one_zero::*;
impl Problem {
pub fn init() -> Self {
Self {}
}
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::init().main().unwrap();
}
use crate as haar_lib;
pub mod graph {
pub mod yen {
#[allow(unused_imports)]
use crate::misc::is_none_or::IsNoneOr;
use crate::{graph::*, num::one_zero::Zero};
use std::ops::{Add, AddAssign};
use std::{cmp::Reverse, collections::BinaryHeap};
type Path = Vec<usize>;
fn shortest_path<D: Direction, E: EdgeTrait>(
g: &Graph<D, E>,
from: usize,
t: usize,
usable: &[bool],
valid: &[Vec<bool>],
) -> Option<(E::Weight, Path)>
where
E::Weight: Zero + Add<Output = E::Weight> + Ord + Eq + Copy,
{
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::new();
dist[from] = Some(E::Weight::zero());
pq.push(Reverse((E::Weight::zero(), from)));
while let Some(Reverse((d, i))) = pq.pop() {
if visited[i] {
continue;
}
visited[i] = true;
for (k, e) in g.nodes[i].edges.iter().enumerate() {
if !valid[i][k] || !usable[e.to()] {
continue;
}
if dist[e.to()].is_none_or(|x| x > 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, E: EdgeTrait>(
g: &Graph<D, E>,
from: usize,
to: usize,
k: usize,
) -> Vec<Option<(E::Weight, Path)>>
where
E::Weight: Zero + Add<Output = E::Weight> + AddAssign + Ord + Eq + Copy,
{
let n = g.len();
let mut result: Vec<Option<(E::Weight, Path)>> = vec![None; k];
let mut stock = BinaryHeap::new();
let mut valid = (0..n)
.map(|i| vec![true; g.nodes[i].edges.len()])
.collect::<Vec<_>>();
for i in 0..k {
if i == 0 {
let usable = vec![true; n];
if let Some((c, p)) = shortest_path(g, from, to, &usable, &valid) {
stock.push(Reverse((c, p)));
}
} else {
let mut prev_path = vec![];
let mut cur = from;
for &u in &result[i - 1].as_ref().unwrap().1 {
prev_path.push(cur);
cur = g.nodes[cur].edges[u].to();
}
prev_path.push(to);
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[u][result[j].as_ref().unwrap().1[k]] = false;
}
}
if let Some((mut c, p)) = shortest_path(g, u, to, &usable, &valid) {
let mut temp = vec![];
for (j, &p) in prev_path.iter().enumerate().take(k) {
let v = result[i - 1].as_ref().unwrap().1[j];
c += g.nodes[p].edges[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[u][result[j].as_ref().unwrap().1[k]] = true;
}
}
for j in 0..i {
if check[j]
&& prev_path[k + 1]
!= g.nodes[u].edges[result[j].as_ref().unwrap().1[k]].to()
{
check[j] = false;
}
}
}
}
if stock.is_empty() {
break;
}
result[i] = stock.pop().map(|a| a.0);
while stock.peek().map(|a| &a.0) == result[i].as_ref() {
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(Clone, Debug)]
pub struct GraphNode<E> {
pub edges: Vec<E>,
}
impl<E: EdgeTrait> IntoIterator for GraphNode<E> {
type Item = E;
type IntoIter = std::vec::IntoIter<Self::Item>;
fn into_iter(self) -> Self::IntoIter {
self.edges.into_iter()
}
}
#[derive(Debug, Clone)]
pub struct Graph<D, E> {
nodes: Vec<GraphNode<E>>,
__phantom: PhantomData<D>,
}
impl<D: Direction, E: EdgeTrait + Clone> Graph<D, E> {
pub fn new(size: usize) -> Self {
Graph {
nodes: vec![GraphNode { edges: vec![] }; size],
__phantom: PhantomData,
}
}
}
impl<E: EdgeTrait + Clone> Graph<Directed, E> {
pub fn add(&mut self, e: E) {
self.nodes[e.from()].edges.push(e);
}
}
impl<E: EdgeTrait + Clone> Extend<E> for Graph<Directed, E> {
fn extend<T: IntoIterator<Item = E>>(&mut self, iter: T) {
iter.into_iter().for_each(|e| self.add(e));
}
}
impl<E: EdgeTrait + Clone> Graph<Undirected, E> {
pub fn add(&mut self, e: E) {
self.nodes[e.from()].edges.push(e.clone());
self.nodes[e.to()].edges.push(e.rev());
}
}
impl<E: EdgeTrait + Clone> Extend<E> for Graph<Undirected, E> {
fn extend<T: IntoIterator<Item = E>>(&mut self, iter: T) {
iter.into_iter().for_each(|e| self.add(e));
}
}
impl<D, E> Graph<D, E> {
pub fn nodes_iter(&self) -> impl Iterator<Item = &GraphNode<E>> {
self.nodes.iter()
}
pub fn node_of(&self, i: usize) -> &GraphNode<E> {
&self.nodes[i]
}
pub fn len(&self) -> usize {
self.nodes.len()
}
pub fn is_empty(&self) -> bool {
self.nodes.is_empty()
}
}
}
pub mod io {
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> {
let c = *self.in_bytes.get(self.in_cur)?;
self.in_cur += 1;
Some(c)
}
#[inline]
pub fn peek(&self) -> Option<u8> {
Some(*self.in_bytes.get(self.in_cur)?)
}
#[inline]
pub fn skip(&mut self) {
while self.peek().is_some_and(|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().is_some_and(|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().is_some_and(|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_f64(&mut self) -> f64 {
self.read_chars()
.into_iter()
.collect::<String>()
.parse()
.unwrap()
}
pub fn read_chars(&mut self) -> Vec<char> {
self.skip();
let mut ret = vec![];
while self.peek().is_some_and(|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 iter {
pub mod join_str {
pub trait JoinStr: Iterator {
fn join_str(self, s: &str) -> String
where
Self: Sized,
Self::Item: ToString,
{
self.map(|x| x.to_string()).collect::<Vec<_>>().join(s)
}
}
impl<I> JoinStr for I where I: Iterator + ?Sized {}
}
}
pub mod macros {
pub mod convert {
#[macro_export]
macro_rules! impl_from {
($(#[$meta:meta])* <const $m:tt: $t:ty>; $from:ty => $into:ty, $f:expr) => {
impl<const $m: $t> From<$from> for $into {
$(#[$meta])*
fn from(value: $from) -> Self {
$f(value)
}
}
};
($(#[$meta:meta])* $from:ty => $into:ty, $f:expr) => {
impl From<$from> for $into {
$(#[$meta])*
fn from(value: $from) -> Self {
$f(value)
}
}
};
}
}
pub mod impl_ops {
#[macro_export]
macro_rules! impl_ops {
(@inner, $(#[$meta:meta])* $tr:ty, $a:ty, $f:expr, $fn:tt; $($bound:tt)*) => {
impl $($bound)* $tr for $a {
type Output = Self;
$(#[$meta])*
fn $fn(self, rhs: Self) -> Self::Output {
$f(self, rhs)
}
}
};
(@inner_assign, $(#[$meta:meta])* $tr:ty, $a:ty, $f:expr, $fn:tt; $($bound:tt)*) => {
impl $($bound)* $tr for $a {
$(#[$meta])*
fn $fn(&mut self, rhs: Self) {
$f(self, rhs)
}
}
};
($(#[$meta:meta])* <const $m:tt: $t:ty>; $trait:ident, $a:ty, $f:expr) => {
impl_ops!(@when $(#[$meta])* $trait, $a, $f; <const $m: $t>);
};
($(#[$meta:meta])* $trait:ident, $a:ty, $f:expr) => {
impl_ops!(@when $(#[$meta])* $trait, $a, $f;);
};
(@when $(#[$meta:meta])* Add, $a:ty, $f:expr; $($bound:tt)*) => {
impl_ops!(@inner, $(#[$meta])* std::ops::Add, $a, $f, add; $($bound)*);
};
(@when $(#[$meta:meta])* Sub, $a:ty, $f:expr; $($bound:tt)*) => {
impl_ops!(@inner, $(#[$meta])* std::ops::Sub, $a, $f, sub; $($bound)*);
};
(@when $(#[$meta:meta])* Mul, $a:ty, $f:expr; $($bound:tt)*) => {
impl_ops!(@inner, $(#[$meta])* std::ops::Mul, $a, $f, mul; $($bound)*);
};
(@when $(#[$meta:meta])* Div, $a:ty, $f:expr; $($bound:tt)*) => {
impl_ops!(@inner, $(#[$meta])* std::ops::Div, $a, $f, div; $($bound)*);
};
(@when $(#[$meta:meta])* AddAssign, $a:ty, $f:expr; $($bound:tt)*) => {
impl_ops!(@inner_assign, $(#[$meta])* std::ops::AddAssign, $a, $f, add_assign; $($bound)*);
};
(@when $(#[$meta:meta])* SubAssign, $a:ty, $f:expr; $($bound:tt)*) => {
impl_ops!(@inner_assign, $(#[$meta])* std::ops::SubAssign, $a, $f, sub_assign; $($bound)*);
};
(@when $(#[$meta:meta])* MulAssign, $a:ty, $f:expr; $($bound:tt)*) => {
impl_ops!(@inner_assign, $(#[$meta])* std::ops::MulAssign, $a, $f, mul_assign; $($bound)*);
};
(@when $(#[$meta:meta])* DivAssign, $a:ty, $f:expr; $($bound:tt)*) => {
impl_ops!(@inner_assign, $(#[$meta])* std::ops::DivAssign, $a, $f, div_assign; $($bound)*);
};
(@when $(#[$meta:meta])* Neg, $a:ty, $f:expr; $($bound:tt)*) => {
impl $($bound)* std::ops::Neg for $a {
type Output = Self;
$(#[$meta])*
fn neg(self) -> Self::Output {
$f(self)
}
}
}
}
}
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 misc {
pub mod is_none_or {
pub trait IsNoneOr<T> {
fn is_none_or(self, f: impl FnOnce(T) -> bool) -> bool;
}
impl<T> IsNoneOr<T> for Option<T> {
#[inline]
fn is_none_or(self, f: impl FnOnce(T) -> bool) -> bool {
!self.is_some_and(|a| !f(a))
}
}
}
}
pub mod num {
pub mod total_f64 {
pub mod one_zero {
use crate::num::one_zero::*;
pub use crate::num::total_f64::*;
impl Zero for Totalf64 {
fn zero() -> Self {
Totalf64(0.0)
}
}
impl One for Totalf64 {
fn one() -> Self {
Totalf64(1.0)
}
}
}
use crate::impl_from;
use crate::impl_ops;
use std::cmp::Ordering;
#[derive(Clone, Copy, Debug, PartialEq, Default)]
pub struct Totalf64(pub f64);
impl PartialOrd for Totalf64 {
fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
Some(self.cmp(other))
}
}
impl Eq for Totalf64 {}
impl Ord for Totalf64 {
fn cmp(&self, other: &Self) -> Ordering {
self.0.partial_cmp(&other.0).unwrap()
}
}
impl_ops!(Add, Totalf64, |s: Self, rhs: Self| Self(s.0 + rhs.0));
impl_ops!(Sub, Totalf64, |s: Self, rhs: Self| Self(s.0 - rhs.0));
impl_ops!(Mul, Totalf64, |s: Self, rhs: Self| Self(s.0 * rhs.0));
impl_ops!(Div, Totalf64, |s: Self, rhs: Self| Self(s.0 / rhs.0));
impl_ops!(AddAssign, Totalf64, |s: &mut Self, rhs: Self| s.0 += rhs.0);
impl_ops!(SubAssign, Totalf64, |s: &mut Self, rhs: Self| s.0 -= rhs.0);
impl_ops!(MulAssign, Totalf64, |s: &mut Self, rhs: Self| s.0 *= rhs.0);
impl_ops!(DivAssign, Totalf64, |s: &mut Self, rhs: Self| s.0 /= rhs.0);
impl_ops!(Neg, Totalf64, |s: Self| Self(-s.0));
impl_from!(f64 => Totalf64, Self);
impl_from!(f32 => Totalf64, |value| Self(value as f64));
impl_from!(Totalf64 => f64, |value: Totalf64| value.0);
}
pub mod one_zero {
pub trait Zero {
fn zero() -> Self;
}
pub trait One {
fn one() -> Self;
}
macro_rules! impl_one_zero {
($($t:ty),*) => {
$(
impl Zero for $t {
fn zero() -> Self { 0 as $t }
}
impl One for $t {
fn one() -> Self { 1 as $t }
}
)*
}
}
impl_one_zero!(u8, u16, u32, u64, u128, usize, i8, i16, i32, i64, i128, isize, f32, f64);
}
}