結果

問題 No.3013 ハチマキ買い星人
ユーザー lp_ql
提出日時 2025-01-25 13:10:18
言語 Rust
(1.83.0 + proconio)
結果
MLE  
実行時間 -
コード長 840 bytes
コンパイル時間 18,874 ms
コンパイル使用メモリ 399,168 KB
実行使用メモリ 1,192,548 KB
最終ジャッジ日時 2025-01-25 22:36:14
合計ジャッジ時間 70,986 ms
ジャッジサーバーID
(参考情報)
judge8 / judge4
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 1
other AC * 23 WA * 5 TLE * 9 MLE * 8
権限があれば一括ダウンロードができます

ソースコード

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(){
        cost[v] = c;
        for &(nv,nc) in &g[v]{
            if cost[nv] == 1<<60{
                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