結果
| 問題 | No.2695 Warp Zone |
| ユーザー |
 Moss_Local
|
| 提出日時 | 2024-03-22 21:52:34 |
| 言語 | Rust (1.77.0) |
| 結果 |
AC
|
| 実行時間 | 75 ms / 2,000 ms |
| コード長 | 5,696 bytes |
| コンパイル時間 | 1,943 ms |
| コンパイル使用メモリ | 197,656 KB |
| 実行使用メモリ | 66,560 KB |
| 最終ジャッジ日時 | 2024-03-22 21:52:38 |
| 合計ジャッジ時間 | 3,515 ms |
|
ジャッジサーバーID （参考情報） |
judge11 / judge14 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 1 ms
6,548 KB |
| testcase_01 | AC | 1 ms
6,548 KB |
| testcase_02 | AC | 1 ms
6,548 KB |
| testcase_03 | AC | 73 ms
66,560 KB |
| testcase_04 | AC | 71 ms
65,280 KB |
| testcase_05 | AC | 70 ms
65,280 KB |
| testcase_06 | AC | 71 ms
66,304 KB |
| testcase_07 | AC | 75 ms
66,560 KB |
| testcase_08 | AC | 1 ms
6,548 KB |
| testcase_09 | AC | 27 ms
26,368 KB |
| testcase_10 | AC | 1 ms
6,548 KB |
| testcase_11 | AC | 9 ms
9,344 KB |
| testcase_12 | AC | 38 ms
36,608 KB |
| testcase_13 | AC | 1 ms
6,548 KB |
| testcase_14 | AC | 47 ms
46,080 KB |
| testcase_15 | AC | 24 ms
23,936 KB |
| testcase_16 | AC | 8 ms
8,448 KB |
| testcase_17 | AC | 15 ms
14,976 KB |
| testcase_18 | AC | 59 ms
57,088 KB |
| testcase_19 | AC | 1 ms
6,548 KB |
| testcase_20 | AC | 52 ms
50,304 KB |
| testcase_21 | AC | 47 ms
45,440 KB |
| testcase_22 | AC | 19 ms
18,048 KB |
| testcase_23 | AC | 37 ms
36,352 KB |
| testcase_24 | AC | 1 ms
6,548 KB |
| testcase_25 | AC | 1 ms
6,548 KB |
| testcase_26 | AC | 1 ms
6,548 KB |
コンパイルメッセージ
warning: variable does not need to be mutable
--> Main.rs:122:9
|
122 | let mut vec: Vec<i64> = read_vec();
| ----^^^
| |
| help: remove this `mut`
|
= note: `#[warn(unused_mut)]` on by default
warning: variable does not need to be mutable
--> Main.rs:128:9
|
128 | let mut vec: Vec<i64> = read_vec();
| ----^^^
| |
| help: remove this `mut`
warning: variable does not need to be mutable
--> Main.rs:133:9
|
133 | let mut vec: Vec<usize> = read_vec();
| ----^^^
| |
| help: remove this `mut`
warning: variable does not need to be mutable
--> Main.rs:139:9
|
139 | let mut vec: Vec<f64> = read_vec();
| ----^^^
| |
| help: remove this `mut`
warning: variable does not need to be mutable
--> Main.rs:144:9
|
144 | let mut vec: Vec<char> = read_vec();
| ----^^^
| |
| help: remove this `mut`
warning: variable does not need to be mutable
--> Main.rs:149:9
|
149 | let mut vec: Vec<usize> = read_vec();
| ----^^^
| |
| help: remove this `mut`
warning: variable does not need to be mutable
--> Main.rs:154:9
|
154 | let mut vec: Vec<i64> = read_vec();
| ----^^^
| |
| help: remove this `mut`
warning: variable does not need to be mutable
--> Main.rs:160:9
|
160 | let mut vec: Vec<usize> = read_vec();
| ----^^^
| |
| help: remove this `mut`
warning: unused variable: `i`
--> Main.rs:199:9
|
199 | for i in 0..n {
| ^ help: if this is intentional, prefix it with an underscore: `_i`
|
= note: `#[warn(unused_variables)]` on by default
warning: variable does not need to be mutable
--> Main.rs:86:17
|
86 | let mut set = ::std::collections::BTreeSet::new();
ソースコード
// -*- coding:utf-8-unix -*-
// #![feature(map_first_last)]
#![allow(dead_code)]
#![allow(unused_imports)]
#![allow(unused_macros)]
// use core::num;
use std::cmp::*;
use std::fmt::*;
use std::hash::*;
use std::iter::FromIterator;
use std::*;
use std::{cmp, collections, fmt, io, iter, ops, str};
const INF: i64 = 1223372036854775807;
const UINF: usize = INF as usize;
const LINF: i64 = 2147483647;
const INF128: i128 = 1223372036854775807000000000000;
const MOD1: i64 = 1000000007;
const MOD9: i64 = 998244353;
const MOD: i64 = MOD9;
// const MOD: i64 = MOD2;
const UMOD: usize = MOD as usize;
const M_PI: f64 = 3.14159265358979323846;
// use proconio::input;
// const MOD: i64 = INF;
use cmp::Ordering::*;
use std::collections::*;
use std::io::stdin;
use std::io::stdout;
use std::io::Write;
macro_rules! p {
($x:expr) => {
//if expr
println!("{}", $x);
};
}
macro_rules! vp {
// vector print separate with space
($x:expr) => {
println!(
"{}",
$x.iter()
.map(|x| x.to_string())
.collect::<Vec<_>>()
.join(" ")
);
};
}
macro_rules! d {
($x:expr) => {
eprintln!("{:?}", $x);
};
}
macro_rules! yn {
($val:expr) => {
if $val {
println!("Yes");
} else {
println!("No");
}
};
}
macro_rules! map{
// declear btreemap
($($key:expr => $val:expr),*) => {
{
let mut map = ::std::collections::BTreeMap::new();
$(
map.insert($key, $val);
)*
map
}
};
}
macro_rules! set{
// declear btreemap
($($key:expr),*) => {
{
let mut set = ::std::collections::BTreeSet::new();
$(
set.insert($key);
)*
set
}
};
}
fn main() {
solve();
}
// use str::Chars;
#[allow(dead_code)]
fn read<T: std::str::FromStr>() -> T {
let mut s = String::new();
std::io::stdin().read_line(&mut s).ok();
s.trim().parse().ok().unwrap()
}
#[allow(dead_code)]
fn read_vec<T: std::str::FromStr>() -> Vec<T> {
read::<String>()
.split_whitespace()
.map(|e| e.parse().ok().unwrap())
.collect()
}
#[allow(dead_code)]
fn read_mat<T: std::str::FromStr>(n: u32) -> Vec<Vec<T>> {
(0..n).map(|_| read_vec()).collect()
}
#[allow(dead_code)]
fn readii() -> (i64, i64) {
let mut vec: Vec<i64> = read_vec();
(vec[0], vec[1])
}
#[allow(dead_code)]
fn readiii() -> (i64, i64, i64) {
let mut vec: Vec<i64> = read_vec();
(vec[0], vec[1], vec[2])
}
#[allow(dead_code)]
fn readuu() -> (usize, usize) {
let mut vec: Vec<usize> = read_vec();
(vec[0], vec[1])
}
#[allow(dead_code)]
fn readff() -> (f64, f64) {
let mut vec: Vec<f64> = read_vec();
(vec[0], vec[1])
}
fn readcc() -> (char, char) {
let mut vec: Vec<char> = read_vec();
(vec[0], vec[1])
}
fn readuuu() -> (usize, usize, usize) {
let mut vec: Vec<usize> = read_vec();
(vec[0], vec[1], vec[2])
}
#[allow(dead_code)]
fn readiiii() -> (i64, i64, i64, i64) {
let mut vec: Vec<i64> = read_vec();
(vec[0], vec[1], vec[2], vec[3])
}
#[allow(dead_code)]
fn readuuuu() -> (usize, usize, usize, usize) {
let mut vec: Vec<usize> = read_vec();
(vec[0], vec[1], vec[2], vec[3])
}
fn read_imat(h: usize) -> Vec<Vec<i64>> {
(0..h).map(|_| read_vec()).collect()
}
fn read_cmat(h: usize) -> Vec<Vec<char>> {
(0..h).map(|_| read::<String>().chars().collect()).collect()
}
fn dijkstra(graph: &Vec<Vec<(usize, usize)>>, start: usize) -> Vec<usize> {
let mut dist = vec![INF as usize; graph.len()];
let mut heap = BinaryHeap::new();
heap.push(Reverse((0 as usize, start)));
dist[start] = 0;
while let Some(Reverse(x)) = heap.pop() {
let cost = x.0;
let v = x.1;
if cost > dist[v] {
continue;
}
for edge in &graph[v] {
let nc = cost + edge.1;
let nv = edge.0;
if nc < dist[nv] {
heap.push(Reverse((nc, nv)));
dist[nv] = nc;
}
}
}
return dist;
}
fn solve() {
let (h, w, n) = readuuu();
let mut node = set![];
node.insert((0, 0));
node.insert((h as i64 - 1, w as i64 - 1));
let mut data = vec![];
for i in 0..n {
let (a, b, c, d) = readiiii();
data.push((a - 1, b - 1, c - 1, d - 1));
node.insert((a - 1, b - 1));
node.insert((c - 1, d - 1));
}
let node_num = node.len();
let mut node_to_idx = map![];
let mut idx_to_node = vec![];
let mut src_idx = 0;
let mut dst_idx = 0;
for (i, &x) in node.iter().enumerate() {
node_to_idx.insert(x, i);
idx_to_node.push(x);
if x == (0, 0) {
src_idx = i;
}
if x == (h as i64 - 1, w as i64 - 1) {
dst_idx = i;
}
}
let mut graph = vec![vec![(0 as usize, 0 as usize); (0) as usize]; (node_num) as usize];
for i in 0..data.len() {
let (a, b, c, d) = data[i];
let i1 = node_to_idx[&(a, b)];
let i2 = node_to_idx[&(c, d)];
// let dist = ((a as i64 - c as i64).abs() + (b as i64 - d as i64).abs()) as usize;
graph[i1].push((i2, 1));
}
for i in 0..node_num {
for j in 0..node_num {
let (a, b) = idx_to_node[i];
let (c, d) = idx_to_node[j];
let dist = ((a as i64 - c as i64).abs() + (b as i64 - d as i64).abs()) as usize;
graph[i].push((j, dist));
}
}
let dist = dijkstra(&graph, src_idx);
p!(dist[dst_idx]);
return;
}