結果
問題 | No.2387 Yokan Factory |
ユーザー | haihamabossu |
提出日時 | 2023-07-21 23:14:38 |
言語 | Rust (1.77.0) |
結果 |
AC
|
実行時間 | 390 ms / 5,000 ms |
コード長 | 4,748 bytes |
コンパイル時間 | 3,451 ms |
コンパイル使用メモリ | 173,320 KB |
実行使用メモリ | 20,464 KB |
最終ジャッジ日時 | 2023-10-21 23:14:33 |
合計ジャッジ時間 | 8,215 ms |
ジャッジサーバーID (参考情報) |
judge12 / judge10 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
4,348 KB |
testcase_01 | AC | 1 ms
4,348 KB |
testcase_02 | AC | 1 ms
4,348 KB |
testcase_03 | AC | 1 ms
4,348 KB |
testcase_04 | AC | 1 ms
4,348 KB |
testcase_05 | AC | 1 ms
4,348 KB |
testcase_06 | AC | 1 ms
4,348 KB |
testcase_07 | AC | 1 ms
4,348 KB |
testcase_08 | AC | 1 ms
4,348 KB |
testcase_09 | AC | 1 ms
4,348 KB |
testcase_10 | AC | 1 ms
4,348 KB |
testcase_11 | AC | 1 ms
4,348 KB |
testcase_12 | AC | 1 ms
4,348 KB |
testcase_13 | AC | 1 ms
4,348 KB |
testcase_14 | AC | 1 ms
4,348 KB |
testcase_15 | AC | 173 ms
17,636 KB |
testcase_16 | AC | 90 ms
19,596 KB |
testcase_17 | AC | 255 ms
19,856 KB |
testcase_18 | AC | 300 ms
20,464 KB |
testcase_19 | AC | 220 ms
12,340 KB |
testcase_20 | AC | 172 ms
11,964 KB |
testcase_21 | AC | 390 ms
18,684 KB |
testcase_22 | AC | 160 ms
10,980 KB |
testcase_23 | AC | 243 ms
12,912 KB |
testcase_24 | AC | 93 ms
11,128 KB |
testcase_25 | AC | 130 ms
9,208 KB |
testcase_26 | AC | 283 ms
14,260 KB |
testcase_27 | AC | 369 ms
17,320 KB |
testcase_28 | AC | 2 ms
4,348 KB |
testcase_29 | AC | 2 ms
4,348 KB |
testcase_30 | AC | 2 ms
4,348 KB |
testcase_31 | AC | 2 ms
4,348 KB |
testcase_32 | AC | 1 ms
4,348 KB |
testcase_33 | AC | 1 ms
4,348 KB |
testcase_34 | AC | 3 ms
4,348 KB |
testcase_35 | AC | 2 ms
4,348 KB |
testcase_36 | AC | 1 ms
4,348 KB |
testcase_37 | AC | 1 ms
4,348 KB |
ソースコード
pub mod binary_search { type T = usize; pub fn binary_search(mut ok: T, mut ng: T, f: impl Fn(T) -> bool) -> T { let cont = |ok: T, ng: T| { let l = ok.min(ng); let r = ok.max(ng); l + 1 < r }; while cont(ok, ng) { let x = (ok + ng) / 2; if f(x) { ok = x; } else { ng = x; } } ok } } pub mod graph { #[derive(Clone, Copy, Debug)] pub struct Edge { pub from: usize, pub to: usize, pub index: usize, pub weight: isize, pub width: isize, } pub struct Graph { pub n: usize, pub m: usize, pub edges: Vec<Vec<Edge>>, } impl Graph { pub fn new(n: usize, m: usize) -> Graph { let edges = vec![vec![]; n]; Graph { n, m, edges } } pub fn add_edge( &mut self, from: usize, to: usize, index: usize, weight: isize, width: isize, ) { let edge = Edge { from, to, index, weight, width, }; self.edges[from].push(edge); } } } pub mod scanner { pub struct Scanner { buf: Vec<String>, } impl Scanner { pub fn new() -> Self { Self { buf: vec![] } } pub fn new_from(source: &str) -> Self { let source = String::from(source); let buf = Self::split(source); Self { buf } } pub fn next<T: std::str::FromStr>(&mut self) -> T { loop { if let Some(x) = self.buf.pop() { return x.parse().ok().expect(""); } let mut source = String::new(); std::io::stdin().read_line(&mut source).expect(""); self.buf = Self::split(source); } } fn split(source: String) -> Vec<String> { source .split_whitespace() .rev() .map(String::from) .collect::<Vec<_>>() } } } use crate::{ binary_search::binary_search, graph::{Edge, Graph}, scanner::Scanner, }; use std::io::Write; fn main() { let mut scanner = Scanner::new(); let out = std::io::stdout(); let mut out = std::io::BufWriter::new(out.lock()); let t: usize = 1; for _ in 0..t { solve(&mut scanner, &mut out); } } fn shortest_path( graph: &Graph, from: usize, w: isize, ) -> (Vec<Option<isize>>, Vec<Option<(usize, Edge)>>) { #[inline] fn add(x: isize, y: isize) -> isize { x + y } #[inline] fn e() -> isize { 0 } use std::cmp::Reverse; let mut que = std::collections::BinaryHeap::<Reverse<(isize, usize)>>::new(); let mut dist = vec![None; graph.n]; let mut prev = vec![None; graph.n]; que.push(Reverse((e(), from))); dist[from] = Some(e()); while let Some(Reverse((d, u))) = que.pop() { if let Some(now_d) = dist[u] { if now_d < d { continue; } } for edge in graph.edges[u].iter() { let &Edge { to: v, weight, width, .. } = edge; if width < w { continue; } let next_d = add(d, weight); if let Some(now_d) = dist[v] { if now_d <= next_d { continue; } } que.push(Reverse((next_d, v))); dist[v] = Some(next_d); prev[v] = Some((u, *edge)); } } (dist, prev) } fn solve(scanner: &mut Scanner, out: &mut std::io::BufWriter<std::io::StdoutLock>) { let n: usize = scanner.next(); let m: usize = scanner.next(); let x: usize = scanner.next(); let mut graph = Graph::new(n, m); for index in 0..m { let from: usize = scanner.next::<usize>() - 1; let to: usize = scanner.next::<usize>() - 1; let weight: isize = scanner.next(); let width: isize = scanner.next(); graph.add_edge(from, to, index, weight, width); graph.add_edge(to, from, index, weight, width); } let ans = binary_search(0, 1e9 as usize + 10, |w| { let dist = shortest_path(&graph, 0, w as isize); dist.0[n - 1].is_some() && dist.0[n - 1].unwrap() <= x as isize }); let ans = if ans == 0 { -1 as isize } else { ans as isize }; writeln!(out, "{}", ans).unwrap(); }