結果
| 問題 | No.3810 Binary Shortest Path Query |
| コンテスト | |
| ユーザー |
akakimidori
|
| 提出日時 | 2026-11-20 21:47:21 |
| 言語 | Rust (1.99.1 + proconio + num + itertools + ACL) |
| 結果 |
AC
不安定
|
| 実行時間 | 112 ms / 2,000 ms |
| + 57µs | |
| コード長 | 7,291 bytes |
| 記録 | |
| コンパイル時間 | 15,210 ms |
| コンパイル使用メモリ | 197,020 KB |
| 実行使用メモリ | 41,408 KB |
| 最終ジャッジ日時 | 2026-11-20 21:47:46 |
| 合計ジャッジ時間 | 20,427 ms |
|
ジャッジサーバーID (参考情報) |
judge2_0 / judge5_0 |
(要ログイン)
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | AC * 30 |
コンパイルメッセージ
warning: use of deprecated constant `std::i128::MAX`: replaced by the `MAX` associated constant on this type
--> src/main.rs:33:26
|
33 | let inf = std::i128::MAX / 2;
| ^^^
|
= note: `#[warn(deprecated)]` on by default
warning: use of deprecated constant `std::i32::MAX`: replaced by the `MAX` associated constant on this type
--> src/main.rs:196:31
|
196 | assert!(n < std::i32::MAX as usize);
| ^^^
ソースコード
use std::io::Write;
fn run() {
input! {
n: usize,
m: usize,
q: usize,
s: [i128; n],
e: [(usize1, usize1, i128); m],
ask: [(usize1, usize1); q],
}
let mut s = s;
let mut dsu = DSU::new(n);
for &(a, b, w) in e.iter() {
if w == 0 {
if let Some((p, c)) = dsu.unite(a, b) {
s[p] = s[p].min(s[c]);
}
}
}
let s = s;
let mut g = vec![vec![]; n];
for (i, &(a, b, w)) in e.iter().enumerate() {
let a = dsu.root(a);
let b = dsu.root(b);
if w == 0 || i > 60 || a == b {
continue;
}
let w = w << (i + 1);
g[a].push((b, w));
g[b].push((a, w));
}
let inf = std::i128::MAX / 2;
let dijkstra = |src: usize, dp: &mut InitArray<i128>| -> i128 {
let mut h = std::collections::BinaryHeap::new();
dp.init();
dp[src] = 0;
let mut res = inf;
h.push((0, src));
while let Some((d, v)) = h.pop() {
let d = -d;
if d > dp[v] {
continue;
}
res = res.min(d + s[v]);
for &(u, w) in g[v].iter() {
if dp[u].chmin(d + w) {
h.push((-dp[u], u));
}
}
}
res
};
let mut a = InitArray::new(inf, n);
let mut b = InitArray::new(inf, n);
let mut calc = |x: usize, y: usize| -> i128 {
let x = dsu.root(x);
let y = dsu.root(y);
let mut ans = dijkstra(x, &mut a) + dijkstra(y, &mut b);
ans.chmin(a[y]);
ans
};
let out = std::io::stdout();
let mut out = std::io::BufWriter::new(out.lock());
for (a, b) in ask {
writeln!(out, "{}", calc(a, b)).ok();
}
}
fn main() {
run();
}
// ---------- begin input macro ----------
// reference: https://qiita.com/tanakh/items/0ba42c7ca36cd29d0ac8
#[macro_export]
macro_rules! input {
(source = $s:expr, $($r:tt)*) => {
let mut iter = $s.split_whitespace();
input_inner!{iter, $($r)*}
};
($($r:tt)*) => {
let s = {
use std::io::Read;
let mut s = String::new();
std::io::stdin().read_to_string(&mut s).unwrap();
s
};
let mut iter = s.split_whitespace();
input_inner!{iter, $($r)*}
};
}
#[macro_export]
macro_rules! input_inner {
($iter:expr) => {};
($iter:expr, ) => {};
($iter:expr, $var:ident : $t:tt $($r:tt)*) => {
let $var = read_value!($iter, $t);
input_inner!{$iter $($r)*}
};
}
#[macro_export]
macro_rules! read_value {
($iter:expr, ( $($t:tt),* )) => {
( $(read_value!($iter, $t)),* )
};
($iter:expr, [ $t:tt ; $len:expr ]) => {
(0..$len).map(|_| read_value!($iter, $t)).collect::<Vec<_>>()
};
($iter:expr, chars) => {
read_value!($iter, String).chars().collect::<Vec<char>>()
};
($iter:expr, bytes) => {
read_value!($iter, String).bytes().collect::<Vec<u8>>()
};
($iter:expr, usize1) => {
read_value!($iter, usize) - 1
};
($iter:expr, $t:ty) => {
$iter.next().unwrap().parse::<$t>().expect("Parse error")
};
}
// ---------- end input macro ----------
// ---------- begin init array ----------
// 初期化配列
// 初期値とサイズを与えて適当にやる系
// new(size, zero): zero埋めした長さsizeの配列を返す
// init(&mut self): 初期化
// init_with(&mut self, f): 非zero な添字とその値をfに渡して初期化
// indexMut でアクセスしたときその履歴を溜め込む
// それ以外でアクセスすると死ぬので注意
//
// 考えるべきこと
// 1. deref で dataへアクセスできるようにしていいか
// derefmut はダメ
// 2. 今のままだと二次元配列の初期化とかには対応できない
// なんか方法を考えたい
#[derive(Clone)]
pub struct InitArray<T> {
data: Vec<T>,
used: Vec<bool>,
list: Vec<u32>,
zero: T,
}
impl<T: Copy> InitArray<T> {
pub fn new(zero: T, size: usize) -> Self {
InitArray {
data: vec![zero; size],
used: vec![false; size],
list: vec![],
zero: zero,
}
}
pub fn init(&mut self) {
self.init_with(|_, _| ());
}
pub fn init_with<F>(&mut self, mut f: F)
where
F: FnMut(usize, T),
{
for x in self.list.drain(..) {
let x = x as usize;
self.used[x] = false;
let v = std::mem::replace(&mut self.data[x], self.zero);
f(x, v);
}
}
}
impl<T> std::ops::Index<usize> for InitArray<T> {
type Output = T;
fn index(&self, pos: usize) -> &Self::Output {
&self.data[pos]
}
}
impl<T> std::ops::IndexMut<usize> for InitArray<T> {
fn index_mut(&mut self, pos: usize) -> &mut Self::Output {
if !self.used[pos] {
self.used[pos] = true;
self.list.push(pos as u32);
}
&mut self.data[pos]
}
}
// ---------- end init array ----------
//---------- begin union_find ----------
pub struct DSU {
p: Vec<i32>,
}
impl DSU {
pub fn new(n: usize) -> DSU {
assert!(n < std::i32::MAX as usize);
DSU { p: vec![-1; n] }
}
pub fn init(&mut self) {
self.p.iter_mut().for_each(|p| *p = -1);
}
pub fn root(&self, mut x: usize) -> usize {
assert!(x < self.p.len());
while self.p[x] >= 0 {
x = self.p[x] as usize;
}
x
}
pub fn same(&self, x: usize, y: usize) -> bool {
assert!(x < self.p.len() && y < self.p.len());
self.root(x) == self.root(y)
}
pub fn unite(&mut self, x: usize, y: usize) -> Option<(usize, usize)> {
assert!(x < self.p.len() && y < self.p.len());
let mut x = self.root(x);
let mut y = self.root(y);
if x == y {
return None;
}
if self.p[x] > self.p[y] {
std::mem::swap(&mut x, &mut y);
}
self.p[x] += self.p[y];
self.p[y] = x as i32;
Some((x, y))
}
pub fn parent(&self, x: usize) -> Option<usize> {
assert!(x < self.p.len());
let p = self.p[x];
if p >= 0 {
Some(p as usize)
} else {
None
}
}
pub fn sum<F>(&self, mut x: usize, mut f: F) -> usize
where
F: FnMut(usize),
{
while let Some(p) = self.parent(x) {
f(x);
x = p;
}
x
}
pub fn size(&self, x: usize) -> usize {
assert!(x < self.p.len());
let r = self.root(x);
(-self.p[r]) as usize
}
}
//---------- end union_find ----------
// ---------- begin chmin, chmax ----------
pub trait ChangeMinMax {
fn chmin(&mut self, x: Self) -> bool;
fn chmax(&mut self, x: Self) -> bool;
}
impl<T: PartialOrd> ChangeMinMax for T {
fn chmin(&mut self, x: Self) -> bool {
*self > x && {
*self = x;
true
}
}
fn chmax(&mut self, x: Self) -> bool {
*self < x && {
*self = x;
true
}
}
}
// ---------- end chmin, chmax ----------
akakimidori