結果

問題 No.3013 ハチマキ買い星人
コンテスト
ユーザー 中秀（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,
};
0