結果

問題 No.807 umg tours
コンテスト
ユーザー k_khr
提出日時 2020-02-01 20:59:42
言語 Rust
(1.83.0 + proconio)
結果
WA  
実行時間 -
コード長 1,947 bytes
コンパイル時間 14,537 ms
コンパイル使用メモリ 378,696 KB
実行使用メモリ 807,200 KB
最終ジャッジ日時 2024-09-18 20:18:32
合計ジャッジ時間 20,580 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other WA * 11 MLE * 1 -- * 14
権限があれば一括ダウンロードができます

ソースコード

diff # 

use std::io::Read;
use std::collections::VecDeque;
use std::cmp;

struct TourPlan {
    spot: usize,
    cost: usize,
    max_cost: usize,
}

fn bfs(st_spot: usize, spots: &Vec<Vec<(usize, usize)>>) -> usize {
    let mut min_cost: usize = std::usize::MAX;
    let mut ticketuse_cost: usize = std::usize::MAX;

    let mut queue: VecDeque<TourPlan> = VecDeque::new();
    queue.push_back( TourPlan { spot: st_spot, cost: 0, max_cost: 0 } );
    while !queue.is_empty() {
        let tp = queue.pop_front().unwrap();
        for &(s, c) in &spots[tp.spot] {
            if s == 1 {
                min_cost = cmp::min(min_cost, tp.cost+c);
                ticketuse_cost = cmp::min(ticketuse_cost, tp.cost - tp.max_cost);
            } else {
                let cost = tp.cost + c;
                let max_cost = cmp::max(tp.max_cost, c);
                if cost > min_cost && cost - max_cost > ticketuse_cost { break; }
                queue.push_back( TourPlan { spot: s, cost, max_cost } );
            }
        }
    }

    min_cost + ticketuse_cost
}


fn main() {
    let mut buf = String::new();
    let stdin = std::io::stdin();
    stdin.lock().read_to_string(&mut buf).unwrap();
    let mut iter = buf.split_whitespace();
    let n = iter.next().unwrap().parse::<usize>().unwrap();
    let m = iter.next().unwrap().parse::<usize>().unwrap();

    // spots[出発地] = [(目的地, cost), ...]
    let mut spots: Vec<Vec<(usize, usize)>> = vec![vec![]; n+1];
    for _ in 0..m {
        let a = iter.next().unwrap().parse::<usize>().unwrap();
        let b = iter.next().unwrap().parse::<usize>().unwrap();
        let c = iter.next().unwrap().parse::<usize>().unwrap();
        spots[a].push((b, c));
        spots[b].push((a, c));
    }

    let mut ans = String::new();
    ans.push_str("\n0\n");
    for i in 2..n+1 {
        let ans_i = bfs(i, &spots);
        ans.push_str(&format!("{}\n", ans_i));
    }
    print!("{}", ans);
}
0