結果

問題 No.807 umg tours
ユーザー k_khrk_khr
提出日時 2020-02-24 15:10:08
言語 Rust
(1.77.0)
結果
WA  
実行時間 -
コード長 1,940 bytes
コンパイル時間 1,373 ms
コンパイル使用メモリ 162,564 KB
実行使用メモリ 812,280 KB
最終ジャッジ日時 2024-04-20 09:51:31
合計ジャッジ時間 8,142 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 WA -
testcase_01 WA -
testcase_02 WA -
testcase_03 WA -
testcase_04 WA -
testcase_05 WA -
testcase_06 WA -
testcase_07 WA -
testcase_08 AC 1 ms
6,940 KB
testcase_09 WA -
testcase_10 WA -
testcase_11 MLE -
testcase_12 -- -
testcase_13 -- -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
testcase_17 -- -
testcase_18 -- -
testcase_19 -- -
testcase_20 -- -
testcase_21 -- -
testcase_22 -- -
testcase_23 -- -
testcase_24 -- -
testcase_25 -- -
権限があれば一括ダウンロードができます

ソースコード

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] {
            let max_cost = cmp::max(tp.max_cost, c);
            if s == 1 {
                min_cost = cmp::min(min_cost, tp.cost+c);
                ticketuse_cost = cmp::min(ticketuse_cost, tp.cost+c - max_cost);
            } else {
                let cost = tp.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("0\n");
    for i in 2..n+1 {
        let ans_i = bfs(i, &spots);
        ans.push_str(&format!("{}\n", ans_i));
    }
    print!("{}", ans);
}
0