結果

問題 No.3111 Toll Optimization
ユーザー zer0-star
提出日時 2025-04-19 00:50:56
言語 Rust
(1.83.0 + proconio)
結果
AC  
実行時間 217 ms / 5,000 ms
コード長 1,832 bytes
コンパイル時間 14,024 ms
コンパイル使用メモリ 386,072 KB
実行使用メモリ 29,696 KB
最終ジャッジ日時 2025-04-19 00:51:19
合計ジャッジ時間 18,591 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 70
権限があれば一括ダウンロードができます
コンパイルメッセージ
warning: constant `DIRS` is never used
 --> src/main.rs:5:7
  |
5 | const DIRS: [(isize, isize); 4] = [(0, 1), (1, 0), (0, -1), (-1, 0)];
  |       ^^^^
  |
  = note: `#[warn(dead_code)]` on by default

warning: method `chmax` is never used
 --> src/main.rs:8:8
  |
7 | trait OrdExt {
  |       ------ method in this trait
8 |     fn chmax(&mut self, other: Self) -> bool;
  |        ^^^^^

warning: variable `N` should have a snake case name
  --> src/main.rs:35:9
   |
35 |         N: usize,
   |         ^ help: convert the identifier to snake case: `n`
   |
   = note: `#[warn(non_snake_case)]` on by default

warning: variable `M` should have a snake case name
  --> src/main.rs:36:9
   |
36 |         M: usize,
   |         ^ help: convert the identifier to snake case: `m`

warning: variable `K` should have a snake case name
  --> src/main.rs:37:9
   |
37 |         K: usize,
   |         ^ help: convert the identifier to snake case (notice the capitalization): `k`

warning: variable `C` should have a snake case name
  --> src/main.rs:38:9
   |
38 |         C: [usize; M],
   |         ^ help: convert the identifier to snake case (notice the capitalization): `c`

ソースコード

diff # 

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

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

const DIRS: [(isize, isize); 4] = [(0, 1), (1, 0), (0, -1), (-1, 0)];

trait OrdExt {
    fn chmax(&mut self, other: Self) -> bool;
    fn chmin(&mut self, other: Self) -> bool;
}

impl<T: Ord> OrdExt for T {
    fn chmax(&mut self, other: Self) -> bool {
        if *self < other {
            *self = other;
            true
        } else {
            false
        }
    }

    fn chmin(&mut self, other: Self) -> bool {
        if *self > other {
            *self = other;
            true
        } else {
            false
        }
    }
}

#[fastout]
fn main() {
    input! {
        N: usize,
        M: usize,
        K: usize,
        C: [usize; M],
        edges: [(Usize1, Usize1); M],
    }

    let mut graph = vec![vec![]; N];

    for (i, &(a, b)) in edges.iter().enumerate() {
        graph[a].push((b, C[i]));
        graph[b].push((a, C[i]));
    }

    let mut priq = BinaryHeap::new();
    let mut locked = vec![vec![false; K + 1]; N];
    let mut dist = vec![vec![std::usize::MAX / 4; K + 1]; N];

    priq.push(Reverse((0, 0, K)));

    while let Some(Reverse((d, v, k))) = priq.pop() {
        if locked[v][k] {
            continue;
        }
        locked[v][k] = true;

        for &(w, c) in graph[v].iter() {
            if locked[w][k] {
                continue;
            }

            if dist[w][k].chmin(d + c) {
                priq.push(Reverse((dist[w][k], w, k)));
            }

            if k > 0 && dist[w][k - 1].chmin(d) {
                priq.push(Reverse((dist[w][k - 1], w, k - 1)));
            }
        }
    }

    let &ans = dist[N - 1].iter().min().unwrap();

    if ans == std::usize::MAX / 4 {
        println!("-1");
    } else {
        println!("{}", ans);
    }
}
0