結果

問題 No.3393 Move on Highway
コンテスト
ユーザー GaLLium
提出日時 2025-11-24 12:56:53
言語 Rust
(1.83.0 + proconio)
結果
AC  
実行時間 630 ms / 3,000 ms
コード長 2,182 bytes
コンパイル時間 12,028 ms
コンパイル使用メモリ 398,428 KB
実行使用メモリ 34,408 KB
最終ジャッジ日時 2025-11-28 21:02:10
合計ジャッジ時間 26,468 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 33
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#![allow(unused)]
#![allow(non_snake_case)]
#![allow(dead_code)]

use std::cmp::Reverse;
fn main() {
    let input_str = std::io::read_to_string(std::io::stdin()).unwrap();
    let mut input = input_str.split_whitespace();
    let mut read_int = ||->usize {input.next().unwrap().parse().unwrap_or(0)};
    
    let (N,M,C) = (read_int(),read_int(),read_int());
   
    let mut G = vec![vec![];N+1];
    for _ in 0..M{
       let (u,v,w) = (read_int(),read_int(),read_int());
       G[u].push((v,w+C));
       G[v].push((u,w+C));
    }
    //頂点1からのダイクストラ(クーポンなし)
    let mut kakutei=vec![false;N+1];
    let mut d1=vec![usize::MAX;N+1];
    let mut pq=std::collections::BinaryHeap::new();
    d1[1]=0;
    pq.push(Reverse((0,1)));
    
    while !(pq.is_empty()) {
        let Reverse((_,pos))=pq.pop().unwrap();
        if kakutei[pos]==true{
            continue;
        }
        kakutei[pos]=true;
        for &(nex,cost) in G[pos].iter(){
            if d1[nex] > d1[pos]+cost{
                d1[nex]=d1[pos]+cost;
                pq.push(Reverse((d1[nex],nex)));
            }            
        }
    }
    
    //頂点Nからのダイクストラ(クーポンあり)
    let mut kakutei=vec![vec![false;N+1];2];
    let mut dN=vec![vec![usize::MAX;N+1];2];
    let mut pq=std::collections::BinaryHeap::new();
    dN[0][N]=0;dN[1][N]=0;
    pq.push(Reverse((0,1,N)));
    
    while !(pq.is_empty()) {
        let Reverse((_,flag,pos))=pq.pop().unwrap();
        if kakutei[flag][pos]==true{
            continue;
        }
        kakutei[flag][pos]=true;
        
        for &(nex,cost) in G[pos].iter(){
            if dN[flag][nex] > dN[flag][pos]+cost{
                dN[flag][nex]=dN[flag][pos]+cost;
                pq.push(Reverse((dN[flag][nex],flag,nex)));
            }            
        }
        if flag == 0 {continue;}
        for &(nex,_) in G[pos].iter(){
            if dN[0][nex] > dN[1][pos]+C{
                dN[0][nex]=dN[1][pos]+C;
                pq.push(Reverse((dN[0][nex],0,nex)));
            }            
        }
    }
    
    for i in 2..=N{
        println!("{}",d1[N].min(d1[i]+dN[0][i]));
    }
}
0