結果
| 問題 |
No.807 umg tours
|
| ユーザー |
 Haar
|
| 提出日時 | 2025-03-18 19:52:00 |
| 言語 | Rust (1.83.0 + proconio) |
| 結果 |
AC
|
| 実行時間 | 897 ms / 4,000 ms |
| コード長 | 11,239 bytes |
| コンパイル時間 | 12,639 ms |
| コンパイル使用メモリ | 400,684 KB |
| 実行使用メモリ | 143,096 KB |
| 最終ジャッジ日時 | 2025-03-18 19:52:27 |
| 合計ジャッジ時間 | 23,188 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 26 |
コンパイルメッセージ
warning: field `from` is never read
--> src/main.rs:172:9
|
171 | pub struct Edge<V, W> {
| ---- field in this struct
172 | from: V,
| ^^^^
|
= note: `#[warn(dead_code)]` on by default
ソースコード
// Bundled at 2025/03/18 19:51:47 +09:00
// Author: Haar
pub mod main {
use super::*;
#[allow(unused_imports)]
use haar_lib::{get, input, iter::join_str::*, utils::fastio::*};
#[allow(unused_imports)]
use std::cell::{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 {}
use haar_lib::mul_graph::dijkstra::*;
impl Problem {
pub fn main(&mut self) -> Result<(), Box<dyn std::error::Error>> {
let mut io = FastIO::new();
let n = io.read_usize();
let m = io.read_usize();
let mut g1 = MulGraph::<usize, u64>::new();
let mut g2 = MulGraph::<(usize, usize), u64>::new();
for _ in 0..m {
let a = io.read_usize();
let b = io.read_usize();
let c = io.read_u64();
g1.add_undirected(a, b, c);
g2.add_undirected((a, 0), (b, 0), c);
g2.add_undirected((a, 1), (b, 1), c);
g2.add_directed((a, 0), (b, 1), 0);
g2.add_directed((b, 0), (a, 1), 0);
}
for i in 1..=n {
g2.add_directed((i, 0), (i, 1), 0);
}
let d1 = dijkstra(&g1, &[1]);
let d2 = dijkstra(&g2, &[(1, 0)]);
for i in 1..=n {
let ans = d1.get(&i).unwrap() + d2.get(&(i, 1)).unwrap();
io.writeln(ans);
}
Ok(())
}
}
}
fn main() {
main::Problem::default().main().unwrap();
}
use crate as haar_lib;
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 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 mul_graph {
pub mod dijkstra {
pub use crate::mul_graph::MulGraph;
use crate::num::{one_zero::Zero, traits::Unsigned};
use std::{
cmp::Reverse,
collections::{BinaryHeap, HashMap, HashSet},
hash::Hash,
ops::Add,
};
pub fn dijkstra<V, W>(graph: &MulGraph<V, W>, src: &[V]) -> HashMap<V, W>
where
V: Hash + Eq + Copy + Ord,
W: Copy + Ord + Zero + Add<Output = W> + Unsigned,
{
let zero = W::zero();
let mut ret = HashMap::new();
let mut heap = BinaryHeap::new();
let mut check = HashSet::new();
for &u in src {
ret.insert(u, zero);
heap.push(Reverse((zero, u)));
}
while let Some(Reverse((d, u))) = heap.pop() {
if check.contains(&u) {
continue;
}
check.insert(u);
for e in graph.neighbours(u) {
let to = e.to;
let cost = e.weight;
match ret.get(&to) {
Some(&d2) if d2 <= d + cost => {}
_ => {
let d = d + cost;
ret.insert(to, d);
if !check.contains(&to) {
heap.push(Reverse((d, to)));
}
}
}
}
}
ret
}
}
use std::collections::HashMap;
use std::hash::Hash;
pub struct Edge<V, W> {
from: V,
to: V,
weight: W,
}
impl<V, W> Edge<V, W> {
pub fn new(from: V, to: V, weight: W) -> Self {
Self { from, to, weight }
}
}
pub struct MulGraph<V, W> {
edges: HashMap<V, Vec<Edge<V, W>>>,
}
impl<V, W> MulGraph<V, W>
where
V: Hash + Eq + Copy,
W: Copy,
{
pub fn new() -> Self {
Self {
edges: HashMap::new(),
}
}
pub fn add_undirected(&mut self, from: V, to: V, weight: W) {
self.add_directed(from, to, weight);
self.add_directed(to, from, weight);
}
pub fn add_directed(&mut self, from: V, to: V, weight: W) {
self.edges
.entry(from)
.or_default()
.push(Edge::new(from, to, weight));
}
pub fn neighbours(&self, cur: V) -> impl Iterator<Item = &Edge<V, W>> {
self.edges.get(&cur).into_iter().flatten()
}
}
}
pub mod num {
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);
}
pub mod traits {
macro_rules! implement {
($tr:ty; $($t:ty),*) => {
$(
impl $tr for $t { }
)*
}
}
pub trait Unsigned {}
implement!(Unsigned; u8, u16, u32, u64, u128, usize);
pub trait Signed {}
implement!(Signed; i8, i16, i32, i64, i128, isize, f32, f64);
pub trait Int {}
implement!(Int; u8, u16, u32, u64, u128, usize, i8, i16, i32, i64, i128, isize);
pub trait Float {}
implement!(Float; 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> {
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();
}
}
}
}