結果

問題 No.807 umg tours
ユーザー k_khrk_khr
提出日時 2020-02-01 20:59:42
言語 Rust
(1.77.0)
結果
WA  
実行時間 -
コード長 1,947 bytes
コンパイル時間 1,183 ms
コンパイル使用メモリ 177,108 KB
実行使用メモリ 816,620 KB
最終ジャッジ日時 2023-10-19 00:20:09
合計ジャッジ時間 8,106 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge11
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
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 WA -
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] {
            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