結果
問題 | No.2387 Yokan Factory |
ユーザー | あさくち |
提出日時 | 2023-07-22 01:44:20 |
言語 | Rust (1.77.0) |
結果 |
AC
|
実行時間 | 680 ms / 5,000 ms |
コード長 | 3,616 bytes |
コンパイル時間 | 8,728 ms |
コンパイル使用メモリ | 168,316 KB |
実行使用メモリ | 12,900 KB |
最終ジャッジ日時 | 2023-10-22 01:25:40 |
合計ジャッジ時間 | 15,295 ms |
ジャッジサーバーID (参考情報) |
judge9 / judge10 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
4,324 KB |
testcase_01 | AC | 1 ms
4,328 KB |
testcase_02 | AC | 1 ms
4,328 KB |
testcase_03 | AC | 1 ms
4,328 KB |
testcase_04 | AC | 1 ms
4,328 KB |
testcase_05 | AC | 1 ms
4,328 KB |
testcase_06 | AC | 1 ms
4,328 KB |
testcase_07 | AC | 1 ms
4,328 KB |
testcase_08 | AC | 1 ms
4,328 KB |
testcase_09 | AC | 1 ms
4,328 KB |
testcase_10 | AC | 1 ms
4,328 KB |
testcase_11 | AC | 1 ms
4,328 KB |
testcase_12 | AC | 1 ms
4,328 KB |
testcase_13 | AC | 1 ms
4,328 KB |
testcase_14 | AC | 1 ms
4,328 KB |
testcase_15 | AC | 213 ms
11,948 KB |
testcase_16 | AC | 171 ms
12,740 KB |
testcase_17 | AC | 399 ms
12,900 KB |
testcase_18 | AC | 505 ms
12,404 KB |
testcase_19 | AC | 321 ms
8,284 KB |
testcase_20 | AC | 246 ms
7,048 KB |
testcase_21 | AC | 680 ms
11,204 KB |
testcase_22 | AC | 230 ms
6,888 KB |
testcase_23 | AC | 396 ms
8,252 KB |
testcase_24 | AC | 220 ms
7,524 KB |
testcase_25 | AC | 207 ms
5,920 KB |
testcase_26 | AC | 478 ms
9,304 KB |
testcase_27 | AC | 672 ms
10,592 KB |
testcase_28 | AC | 3 ms
4,328 KB |
testcase_29 | AC | 3 ms
4,328 KB |
testcase_30 | AC | 3 ms
4,328 KB |
testcase_31 | AC | 2 ms
4,328 KB |
testcase_32 | AC | 2 ms
4,328 KB |
testcase_33 | AC | 1 ms
4,328 KB |
testcase_34 | AC | 4 ms
4,328 KB |
testcase_35 | AC | 3 ms
4,328 KB |
testcase_36 | AC | 2 ms
4,328 KB |
testcase_37 | AC | 1 ms
4,328 KB |
ソースコード
use std::cmp::Ordering; use std::cmp::Reverse; use std::collections::BinaryHeap; // use std::io; const INF: usize = 1_000_000_000_000_000_000; #[derive(Debug, Eq, PartialEq)] struct Vertex { /// 重み weight: usize, /// 頂点番号 vertex_number: usize, } impl Ord for Vertex { fn cmp(&self, other: &Self) -> Ordering { self.weight.cmp(&other.weight) } } impl std::cmp::PartialOrd for Vertex { fn partial_cmp(&self, other: &Vertex) -> Option<Ordering> { Some(self.cmp(other)) } } fn main() { let (n, m, x) = input_tuple(); let u_v_a_b = input_tuple_vec::<usize>(m); let mut ok: isize = 0; let mut ng = 1 << 60; while (ok - ng).abs() > 1 { let mid = (ok + ng) / 2; let solve = || { // ある頂点からの辺と重み let mut list = vec![Vec::new(); n]; for &(u, v, a, b) in &u_v_a_b { if b as isize >= mid { list[u - 1].push((v - 1, a)); list[v - 1].push((u - 1, a)); } } let start = 0; // 始点から各頂点までの最短コスト let mut costs = vec![INF; n]; costs[start] = 0; let mut priority_queue = BinaryHeap::new(); priority_queue.push(Reverse(Vertex { vertex_number: start, weight: 0, })); while let Some(Reverse(point)) = priority_queue.pop() { let current = point.vertex_number; let current_cost = point.weight; if costs[current] != current_cost { continue; } for &(next, edge_weight) in &list[current] { let next_cost = current_cost + edge_weight; if next_cost >= costs[next] { continue; } costs[next] = next_cost; priority_queue.push(Reverse(Vertex { vertex_number: next, weight: next_cost, })); } } costs[n - 1] <= x }; if solve() { ok = mid; } else { ng = mid; } } if ok != 0 { println!("{}", ok); } else { println!("-1"); } } fn input_tuple<T>() -> (T, T, T) where T: std::str::FromStr, <T as std::str::FromStr>::Err: std::fmt::Debug, { let stdin = std::io::stdin(); let mut buf = String::new(); stdin.read_line(&mut buf).unwrap(); buf = buf.trim_end().to_owned(); let mut iter = buf.split_whitespace(); let n = iter.next().unwrap().parse().unwrap(); let m = iter.next().unwrap().parse().unwrap(); let l = iter.next().unwrap().parse().unwrap(); (n, m, l) } fn input_tuple_vec<T>(n: usize) -> Vec<(T, T, T, T)> where T: std::str::FromStr, <T as std::str::FromStr>::Err: std::fmt::Debug, { // タプルのベクタ let stdin = std::io::stdin(); let mut s_t_d = Vec::with_capacity(n); for _ in 0..n { let mut buf = String::new(); stdin.read_line(&mut buf).unwrap(); buf = buf.trim_end().to_owned(); let mut iter = buf.split_whitespace(); let s = iter.next().unwrap().parse().unwrap(); let t = iter.next().unwrap().parse().unwrap(); let d = iter.next().unwrap().parse().unwrap(); let x = iter.next().unwrap().parse().unwrap(); s_t_d.push((s, t, d, x)); } s_t_d }