結果

問題 No.3013 ハチマキ買い星人
ユーザー lp_ql
提出日時 2025-01-25 13:19:27
言語 Rust
(1.83.0 + proconio)
結果
AC  
実行時間 285 ms / 2,000 ms
コード長 827 bytes
コンパイル時間 12,963 ms
コンパイル使用メモリ 378,508 KB
実行使用メモリ 33,152 KB
最終ジャッジ日時 2025-01-25 22:43:15
合計ジャッジ時間 19,347 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 45
権限があれば一括ダウンロードができます

ソースコード

diff # 

use std::{cmp::Reverse, collections::BinaryHeap};
use proconio::{input, marker::Usize1};
fn main() {
    input!{
        n: usize,
        m: usize,
        p: usize,
        y: usize,
        abc: [(Usize1,Usize1,usize);m],
        de: [(Usize1,usize);p],
    }
    let mut g = vec![vec![];n];
    for (a,b,c) in abc{
        g[a].push((b,c));
        g[b].push((a,c));
    }
    let mut cost = vec![1<<60;n];
    let mut pq = BinaryHeap::new();
    pq.push((Reverse(0),0));
    while let Some((Reverse(c),v)) = pq.pop(){
        if cost[v] != 1<<60{continue;}
        cost[v] = c;
        for &(nv,nc) in &g[v]{
            pq.push((Reverse(c+nc),nv))
        }
    }
    let mut h = vec![1<<60;n];
    for (d,e) in de{
        h[d] = e
    }
    println!("{}",(0..n).map(|i| (y.max(cost[i])-cost[i])/h[i]).max().unwrap());
}
0