結果

問題 No.3013 ハチマキ買い星人
ユーザー toyboot4e
提出日時 2025-01-25 14:06:58
言語 Rust
(1.83.0 + proconio)
結果
WA  
実行時間 -
コード長 2,827 bytes
コンパイル時間 15,446 ms
コンパイル使用メモリ 376,860 KB
実行使用メモリ 35,200 KB
最終ジャッジ日時 2025-01-25 23:07:40
合計ジャッジ時間 18,258 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge9
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 31 WA * 14
権限があれば一括ダウンロードができます
コンパイルメッセージ
warning: field `parent` is never read
 --> src/main.rs:9:5
  |
7 | struct Dijkstra {
  |        -------- field in this struct
8 |     distance: Vec<usize>,
9 |     parent: Vec<usize>,
  |     ^^^^^^
  |
  = note: `#[warn(dead_code)]` on by default

warning: method `get_path` is never used
  --> src/main.rs:51:12
   |
12 | impl Dijkstra {
   | ------------- method in this implementation
...
51 |     pub fn get_path(&self, target: usize) -> Vec<usize> {
   |            ^^^^^^^^

ソースコード

diff # 

use proconio::input;
use std::{cmp::Reverse, collections::BinaryHeap};

// Thanks: https://qiita.com/okaponta_/items/018d0cd4f38ead3675c0
const INF: usize = 1 << 62;

struct Dijkstra {
    distance: Vec<usize>,
    parent: Vec<usize>,
}

impl Dijkstra {
    // n:usize 頂点の数
    // edge: Vec<Vec<(usize,usize)>> edge[i] = [(2,3), (3,1), (頂点への道,重み)]
    // init:usize どの頂点を起点に考えるか
    pub fn new(n: usize, edge: Vec<Vec<(usize, usize)>>, init: usize) -> Self {
        let mut distance = vec![INF; n];
        let mut parent = vec![INF; n];
        let mut heap = BinaryHeap::new();
        for i in 0..n {
            if i == init {
                // 始点は0
                // BinaryHeapはpopで最大値を取得するので、Reverse()で最小値を取得できるようにする
                heap.push((Reverse(0), i));
            }
            heap.push((Reverse(INF), i));
        }
        while let Some((Reverse(d), target)) = heap.pop() {
            if distance[target] < d {
                // 既にもっと短い経路が見つかってるので無視
                continue;
            }
            distance[target] = d;
            for &(next, cost) in &edge[target] {
                if distance[next] > d + cost {
                    // 短い経路の候補となるので処理を行う
                    distance[next] = d + cost;
                    heap.push((Reverse(distance[next]), next));
                    // ひとつ前の頂点を保存しておく
                    parent[next] = target;
                }
            }
        }
        Self { distance, parent }
    }

    pub fn distance(&self, target: usize) -> usize {
        self.distance[target]
    }

    pub fn get_path(&self, target: usize) -> Vec<usize> {
        let mut current = target;
        let mut res = vec![current];
        while self.parent[current] != INF as usize {
            let next = self.parent[current];
            res.push(next);
            current = next;
        }
        res.reverse();
        res
    }
}

fn main() {
    input! {
        n: usize,
        m: usize,
        p: usize,
        y: usize,
        uvws: [(usize, usize, usize); m],
        // at D, price E
        des: [(usize, usize); p],
    }

    let mut es = Vec::with_capacity(n);
    for _ in 0..n {
        es.push(Vec::new())
    }

    for (u, v, w) in uvws.iter().cloned() {
        es[u - 1].push((v - 1, w));
    }

    let dj = Dijkstra::new(n, es, 0);

    let res = des
        .iter()
        .cloned()
        .map(|(v_, e)| {
            let d = dj.distance(v_ - 1);
            if d == INF {
                0
            } else {
                (y - d).max(0) / e
            }
        })
        .max()
        .unwrap();

    println!("{}", res);
}
0