結果

問題 No.3013 ハチマキ買い星人
ユーザー 中秀(nakahide)中秀(nakahide)
提出日時 2025-01-25 15:58:51
言語 Rust
(1.83.0 + proconio)
結果
AC  
実行時間 189 ms / 2,000 ms
コード長 1,670 bytes
コンパイル時間 14,694 ms
コンパイル使用メモリ 379,136 KB
実行使用メモリ 30,588 KB
最終ジャッジ日時 2025-01-25 23:50:00
合計ジャッジ時間 17,175 ms
ジャッジサーバーID
(参考情報)
judge4 / judge12
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 1
other AC * 45
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

fn main() {
input!{
// ,,,
n: usize, m: usize, p: usize, y: usize,
}
// (,)
let mut uv = vec![Vec::new(); n];
for _ in 0..m {
input!{
a: Usize1, b: Usize1, c : usize,
}
uv[a].push((b, c));
uv[b].push((a, c));
}
//
let mut shops = vec![INF; n];
for _ in 0..p {
input!{
d: Usize1, e: usize,
}
shops[d] = e;
}
//
let mut min_cost = vec![INF; n];
min_cost[0] = 0;
let mut hp = BinaryHeap::new();
//
hp.push(Reverse((0, 0)));
while hp.len() > 0 {
let (cost_yen, cpos) = hp.pop().unwrap().0;
if min_cost[cpos] < cost_yen { continue; }
for &(npos, cost) in &uv[cpos] {
let ncost_yen = min_cost[cpos] + cost;
if min_cost[npos] > ncost_yen {
min_cost[npos] = ncost_yen;
hp.push(Reverse((ncost_yen, npos)));
}
}
}
let mut ans = 0;
for i in 0..n {
let mut rest = 0;
if y > min_cost[i] {
rest = y - min_cost[i];
}
ans = max(ans, rest / shops[i]);
}
println!("{}", ans);
}
// const MOD17: usize = 1000000007;
// const MOD93: usize = 998244353;
const INF: usize = 1 << 60;
// let dx = vec![!0, 0, 1, 0]; //
// let dy = vec![0, !0, 0, 1]; //
// let d = vec!{(!0, 0), (0, !0), (1, 0), (0, 1)}; //
#[allow(unused)]
use proconio::{input, marker::Chars, marker::Usize1};
#[allow(unused)]
use std::{
mem::swap,
cmp::min, cmp::max,
cmp::Reverse,
collections::HashSet, collections::BTreeSet,
collections::HashMap, collections::BTreeMap,
collections::BinaryHeap,
collections::VecDeque,
iter::FromIterator,
};
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0