結果
問題 | No.1995 CHIKA Road |
ユーザー | phspls |
提出日時 | 2022-09-20 00:20:59 |
言語 | Rust (1.77.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 3,261 bytes |
コンパイル時間 | 8,497 ms |
コンパイル使用メモリ | 172,808 KB |
実行使用メモリ | 53,328 KB |
最終ジャッジ日時 | 2023-08-23 19:15:02 |
合計ジャッジ時間 | 8,512 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge15 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
4,376 KB |
testcase_01 | AC | 1 ms
4,376 KB |
testcase_02 | AC | 2 ms
4,380 KB |
testcase_03 | AC | 1 ms
4,376 KB |
testcase_04 | AC | 1 ms
4,380 KB |
testcase_05 | WA | - |
testcase_06 | AC | 14 ms
4,888 KB |
testcase_07 | AC | 55 ms
12,448 KB |
testcase_08 | AC | 2 ms
4,380 KB |
testcase_09 | AC | 1 ms
4,376 KB |
testcase_10 | AC | 54 ms
10,516 KB |
testcase_11 | WA | - |
testcase_12 | WA | - |
testcase_13 | WA | - |
testcase_14 | WA | - |
testcase_15 | WA | - |
testcase_16 | AC | 24 ms
6,976 KB |
testcase_17 | AC | 130 ms
23,020 KB |
testcase_18 | AC | 231 ms
37,088 KB |
testcase_19 | AC | 236 ms
37,068 KB |
testcase_20 | AC | 116 ms
20,940 KB |
testcase_21 | AC | 103 ms
19,584 KB |
testcase_22 | AC | 213 ms
33,124 KB |
testcase_23 | AC | 54 ms
12,632 KB |
testcase_24 | AC | 180 ms
29,540 KB |
testcase_25 | AC | 28 ms
7,904 KB |
testcase_26 | AC | 74 ms
13,972 KB |
testcase_27 | AC | 173 ms
28,632 KB |
testcase_28 | AC | 103 ms
19,688 KB |
testcase_29 | AC | 232 ms
35,924 KB |
testcase_30 | AC | 27 ms
7,660 KB |
testcase_31 | AC | 12 ms
4,896 KB |
testcase_32 | AC | 38 ms
9,436 KB |
testcase_33 | AC | 168 ms
28,224 KB |
testcase_34 | AC | 14 ms
5,224 KB |
testcase_35 | AC | 64 ms
13,400 KB |
testcase_36 | AC | 78 ms
15,216 KB |
testcase_37 | AC | 209 ms
31,692 KB |
testcase_38 | AC | 139 ms
24,284 KB |
testcase_39 | AC | 12 ms
4,584 KB |
コンパイルメッセージ
warning: field `n` is never read --> Main.rs:7:5 | 6 | struct Dijkstra { | -------- field in this struct 7 | n: usize, | ^ | = note: `Dijkstra` has derived impls for the traits `Clone` and `Debug`, but these are intentionally ignored during dead code analysis = note: `#[warn(dead_code)]` on by default warning: associated function `reconstruct` is never used --> Main.rs:49:8 | 49 | fn reconstruct(&self, startpoint: usize, endpoint: usize) -> Vec<(usize, usize)> { | ^^^^^^^^^^^ warning: 2 warnings emitted
ソースコード
use std::{cmp::Reverse, collections::{BinaryHeap, BTreeSet, HashMap}}; const INF: usize = 1usize << 60; #[derive(Debug, Clone)] struct Dijkstra { n: usize, pathcosts: Vec<Vec<(usize, usize)>>, pathcostsrev: Vec<Vec<(usize, usize)>>, costs: Vec<usize> } impl Dijkstra { fn new(n: usize) -> Self { Self { n: n , pathcosts: vec![vec![]; n] , pathcostsrev: vec![vec![]; n] , costs: vec![INF; n] } } fn pusha2b(&mut self, a: usize, b: usize, cost: usize) { self.pathcosts[a].push((cost, b)); self.pathcostsrev[b].push((cost, a)); } fn get_cost(&self, idx: usize) -> usize { self.costs[idx] } fn solve(&mut self, startpoint: usize) { let mut que = BinaryHeap::new(); que.push(Reverse((0, startpoint))); self.costs[startpoint] = 0; while let Some(Reverse(p)) = que.pop() { let cost = p.0; let dest = p.1; if cost > self.costs[dest] { continue; } for &p2 in self.pathcosts[dest].iter() { if self.costs[dest] + p2.0 < self.costs[p2.1] { self.costs[p2.1] = self.costs[dest] + p2.0; que.push(Reverse((self.costs[p2.1], p2.1))); } } } } fn reconstruct(&self, startpoint: usize, endpoint: usize) -> Vec<(usize, usize)> { let mut ret = vec![]; if self.costs[endpoint] == INF { return ret; } let mut current = endpoint; while current != startpoint { for &(cost, u) in self.pathcostsrev[current].iter() { if self.costs[current] == self.costs[u] + cost { let prev = current; current = u; ret.push((current, prev)); break; } } } ret.reverse(); ret } } fn main() { let mut nm = String::new(); std::io::stdin().read_line(&mut nm).ok(); let nm: Vec<usize> = nm.trim().split_whitespace().map(|s| s.parse().unwrap()).collect(); let n = nm[0]; let m = nm[1]; let mut lines = Vec::with_capacity(m); let mut used = BTreeSet::new(); used.insert(n-1); for _ in 0..m { let mut ab = String::new(); std::io::stdin().read_line(&mut ab).ok(); let ab: Vec<usize> = ab.trim().split_whitespace().map(|s| s.parse().unwrap()).collect(); let a = ab[0]; let b = ab[1]; let dist = 2*b - 2*a - 1; let a = a-1; let b = b-1; lines.push((a, b, dist)); used.insert(a); used.insert(b); } let mut mapping = HashMap::new(); for (i, &v) in used.iter().enumerate() { mapping.insert(v, i); } let mut paths = Dijkstra::new(used.len()); for &(u, v, w) in lines.iter() { paths.pusha2b(*mapping.get(&u).unwrap(), *mapping.get(&v).unwrap(), w) } let used = used.into_iter().collect::<Vec<usize>>(); for i in 0..used.len()-1 { let u = used[i]; let v = used[i+1]; let dist = (v - u) * 2; paths.pusha2b(i, i+1, dist); } paths.solve(0); println!("{}", paths.get_cost(used.len()-1)); }