結果
問題 | No.3 ビットすごろく |
ユーザー |
|
提出日時 | 2020-10-01 23:21:13 |
言語 | Rust (1.83.0 + proconio) |
結果 |
WA
|
実行時間 | - |
コード長 | 6,655 bytes |
コンパイル時間 | 11,026 ms |
コンパイル使用メモリ | 391,604 KB |
実行使用メモリ | 6,948 KB |
最終ジャッジ日時 | 2024-07-07 06:33:55 |
合計ジャッジ時間 | 12,479 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | WA * 33 |
ソースコード
use std::cmp::Ordering;use std::collections::BinaryHeap;fn getline() -> String {let mut __ret = String::new();std::io::stdin().read_line(&mut __ret).ok();return __ret;}fn getline_as_u32() -> u32 {let l = getline();let nlv: Vec<_> = l.trim().split(' ').collect();nlv[0].parse::<u32>().unwrap()}#[derive(Copy, Clone, Eq, PartialEq)]struct State {cost: usize,position: usize,}// The priority queue depends on `Ord`.// Explicitly implement the trait so the queue becomes a min-heap// instead of a max-heap.impl Ord for State {fn cmp(&self, other: &State) -> Ordering {// Notice that the we flip the ordering on costs.// In case of a tie we compare positions - this step is necessary// to make implementations of `PartialEq` and `Ord` consistent.other.cost.cmp(&self.cost).then_with(|| self.position.cmp(&other.position))}}// `PartialOrd` needs to be implemented as well.impl PartialOrd for State {fn partial_cmp(&self, other: &State) -> Option<Ordering> {Some(self.cmp(other))}}// Each node is represented as an `usize`, for a shorter implementation.#[derive(Debug)]struct Edge {node: usize,cost: usize,}// Dijkstra's shortest path algorithm.// Start at `start` and use `dist` to track the current shortest distance// to each node. This implementation isn't memory-efficient as it may leave duplicate// nodes in the queue. It also uses `usize::MAX` as a sentinel value,// for a simpler implementation.fn shortest_path(adj_list: &Vec<Vec<Edge>>, start: usize, goal: usize) -> Option<usize> {// dist[node] = current shortest distance from `start` to `node`let mut dist: Vec<_> = (0..adj_list.len()).map(|_| usize::MAX).collect();let mut heap = BinaryHeap::new();// We're at `start`, with a zero costdist[start] = 0;heap.push(State {cost: 0,position: start,});// Examine the frontier with lower cost nodes first (min-heap)while let Some(State { cost, position }) = heap.pop() {// Alternatively we could have continued to find all shortest pathsif position == goal {return Some(cost);}// Important as we may have already found a better wayif cost > dist[position] {continue;}// For each node we can reach, see if we can find a way with// a lower cost going through this nodefor edge in &adj_list[position] {let next = State {cost: cost + edge.cost,position: edge.node,};// If so, add it to the frontier and continueif next.cost < dist[next.position] {heap.push(next);// Relaxation, we have now found a better waydist[next.position] = next.cost;}}}// Goal not reachableNone}// n を与えられると graph を返す関数を用意したいfn gen_bit_graph(n: u32) -> Vec<Vec<Edge>> {// 10進数から進める数を算出するfn number_to_dice(number: u32) -> u32 {format!("{:b}", number).to_string().chars().collect::<Vec<char>>().iter().map(|x| x.to_digit(10).unwrap()).sum::<u32>()}// ラベル番号が与えられると 有向エッジを返す。なおすべてのコストは1固定fn gen_node(number: u32, _n: u32) -> Vec<Edge> {return if number == _n || number == 0 {vec![]} else if number == 1 {vec![Edge { node: 2, cost: 1 }]} else {// ゴールを超えたら戻るやつ。このあたり微妙let dice = number_to_dice(number);let positive: u32 = if (number + dice) < _n {number + dice} else {_n * 2 - (number + dice)};let negative: u32 = number - number_to_dice(number);vec![Edge {node: positive as usize,cost: 1,},Edge {node: negative as usize,cost: 1,},]};}(0..=n).map(|x| gen_node(x, n)).collect()}fn main() {let n: u32 = getline_as_u32();// ビットすごろくをすべての辺が重み1の有向グラフ 最短経路問題に変換する// 数値をビット合計に変換(たぶんいけた)// ノードを生成する// グラフを生成する// ダイクストラ適用// This is the directed graph we're going to use.// The node numbers correspond to the different states,// and the edge weights symbolize the cost of moving// from one node to another.// Note that the edges are one-way.//// 7// +-----------------+// | |// v 1 2 | 2// 0 -----> 1 -----> 3 ---> 4// | ^ ^ ^// | | 1 | |// | | | 3 | 1// +------> 2 -------+ |// 10 | |// +---------------+//// The graph is represented as an adjacency list where each index,// corresponding to a node value, has a list of outgoing edges.// Chosen for its efficiency.// let graph = vec![// // Node 0// vec![Edge { node: 2, cost: 10 }, Edge { node: 1, cost: 1 }],// // Node 1// vec![Edge { node: 3, cost: 2 }],// // Node 2// vec![// Edge { node: 1, cost: 1 },// Edge { node: 3, cost: 3 },// Edge { node: 4, cost: 1 },// ],// // Node 3// vec![Edge { node: 0, cost: 7 }, Edge { node: 4, cost: 2 }],// // Node 4// vec![],// ];// assert_eq!(shortest_path(&graph, 0, 1), Some(1));// assert_eq!(shortest_path(&graph, 0, 3), Some(3));// assert_eq!(shortest_path(&graph, 3, 0), Some(7));// assert_eq!(shortest_path(&graph, 0, 4), Some(5));// assert_eq!(shortest_path(&graph, 4, 0), None);let graph = gen_bit_graph(n);println!("{:?}", graph);match shortest_path(&graph, 1, n as usize) {Some(x) => println!("{}", x + 1), // 初手もカウントに入れることを考慮None => println!("-1"),}}