結果
問題 | No.3013 ハチマキ買い星人 |
ユーザー |
|
提出日時 | 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 |
ソースコード
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,};