結果

問題 No.3013 ハチマキ買い星人
ユーザー The_Bouningeeeen
提出日時 2025-01-25 13:37:18
言語 Rust
(1.83.0 + proconio)
結果
TLE  
実行時間 -
コード長 1,041 bytes
コンパイル時間 19,478 ms
コンパイル使用メモリ 379,280 KB
実行使用メモリ 43,648 KB
最終ジャッジ日時 2025-01-25 22:53:45
合計ジャッジ時間 106,439 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge10
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 15 TLE * 30
権限があれば一括ダウンロードができます

ソースコード

diff # 

use proconio::{input, marker::Usize1};

fn main() {
    input! {
        n: usize,
        m: usize,
        p: usize,
        y: isize,
        abc: [(Usize1, Usize1, isize); m],
        de: [(Usize1, isize); 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 stores = vec![isize::MAX; n];
    for (d, e) in de {
        stores[d] = e;
    }

    let mut ans = 0;
    dfs(0, y, &mut ans, &mut vec![false; n], &graph, &stores);
    println!("{}", ans);
}

fn dfs(
    pos: usize,
    money: isize,
    ans: &mut isize,
    visited: &mut Vec<bool>,
    graph: &Vec<Vec<(usize, isize)>>,
    stores: &Vec<isize>,
) {
    if money == 0 {
        return;
    }

    visited[pos] = true;
    *ans = (*ans).max(money / stores[pos]);

    for &(next, robbed) in &graph[pos] {
        if visited[next] {
            continue;
        }

        dfs(next, (money - robbed).max(0), ans, visited, graph, stores);
    }

    visited[pos] = false;
}
0