結果
問題 | No.3013 ハチマキ買い星人 |
ユーザー |
|
提出日時 | 2025-01-25 13:58:55 |
言語 | Rust (1.83.0 + proconio) |
結果 |
AC
|
実行時間 | 212 ms / 2,000 ms |
コード長 | 1,058 bytes |
コンパイル時間 | 12,178 ms |
コンパイル使用メモリ | 401,296 KB |
実行使用メモリ | 32,952 KB |
最終ジャッジ日時 | 2025-01-25 23:04:21 |
合計ジャッジ時間 | 17,796 ms |
ジャッジサーバーID (参考情報) |
judge10 / judge7 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 45 |
ソースコード
use proconio::{input, marker::Usize1}; use std::collections::BinaryHeap; fn main() { input! { n: usize, m: usize, p: usize, y: usize, abc: [(Usize1, Usize1, usize); m], de: [(Usize1, usize); p], } let mut graph = vec![vec![]; n]; for (a, b, c) in abc { graph[a].push((b, c)); graph[b].push((a, c)) } let mut rest_money = vec![0; n]; rest_money[0] = y; let mut heap = BinaryHeap::new(); heap.push((y, 0)); while let Some((money, pos)) = heap.pop() { if rest_money[pos] > money { continue; } for &(next, robbed) in &graph[pos] { let new_money = (money - robbed).max(0); if new_money == 0 || rest_money[next] >= new_money { continue; } rest_money[next] = new_money; heap.push((rest_money[next], next)); } } let mut ans = 0; for (d, e) in de { ans = ans.max(rest_money[d] / e); } println!("{}", ans); }