結果
問題 | 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);}