結果
| 問題 | No.1473 おでぶなおばけさん |
| ユーザー |
 Moss_Local
|
| 提出日時 | 2021-04-09 22:46:28 |
| 言語 | Rust (1.77.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 7,910 bytes |
| コンパイル時間 | 3,476 ms |
| コンパイル使用メモリ | 153,560 KB |
| 実行使用メモリ | 15,708 KB |
| 最終ジャッジ日時 | 2023-09-07 12:22:42 |
| 合計ジャッジ時間 | 6,633 ms |
|
ジャッジサーバーID （参考情報） |
judge12 / judge11 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 1 ms
4,376 KB |
| testcase_01 | AC | 1 ms
4,380 KB |
| testcase_02 | AC | 64 ms
14,620 KB |
| testcase_03 | AC | 41 ms
11,780 KB |
| testcase_04 | AC | 31 ms
9,104 KB |
| testcase_05 | AC | 10 ms
4,376 KB |
| testcase_06 | AC | 46 ms
11,672 KB |
| testcase_07 | AC | 59 ms
15,608 KB |
| testcase_08 | AC | 65 ms
15,708 KB |
| testcase_09 | AC | 63 ms
15,604 KB |
| testcase_10 | AC | 29 ms
5,284 KB |
| testcase_11 | AC | 28 ms
5,268 KB |
| testcase_12 | AC | 27 ms
5,172 KB |
| testcase_13 | AC | 19 ms
4,376 KB |
| testcase_14 | AC | 13 ms
4,376 KB |
| testcase_15 | AC | 25 ms
5,156 KB |
| testcase_16 | AC | 27 ms
5,260 KB |
| testcase_17 | AC | 3 ms
4,376 KB |
| testcase_18 | AC | 3 ms
4,376 KB |
| testcase_19 | AC | 25 ms
5,220 KB |
| testcase_20 | AC | 35 ms
10,480 KB |
| testcase_21 | AC | 37 ms
7,500 KB |
| testcase_22 | WA | - |
| testcase_23 | WA | - |
| testcase_24 | WA | - |
| testcase_25 | WA | - |
| testcase_26 | AC | 47 ms
10,720 KB |
| testcase_27 | WA | - |
| testcase_28 | AC | 56 ms
15,196 KB |
| testcase_29 | WA | - |
| testcase_30 | AC | 42 ms
8,680 KB |
| testcase_31 | AC | 58 ms
15,140 KB |
| testcase_32 | AC | 33 ms
11,600 KB |
| testcase_33 | AC | 33 ms
10,136 KB |
| testcase_34 | AC | 20 ms
6,572 KB |
| testcase_35 | AC | 16 ms
5,484 KB |
| testcase_36 | WA | - |
| testcase_37 | AC | 44 ms
11,244 KB |
| testcase_38 | WA | - |
| testcase_39 | AC | 28 ms
5,344 KB |
| testcase_40 | AC | 29 ms
5,328 KB |
| testcase_41 | AC | 27 ms
5,176 KB |
| testcase_42 | AC | 27 ms
5,256 KB |
| testcase_43 | AC | 33 ms
11,412 KB |
| testcase_44 | AC | 33 ms
11,368 KB |
| testcase_45 | AC | 34 ms
11,456 KB |
| testcase_46 | AC | 38 ms
10,276 KB |
| testcase_47 | AC | 53 ms
11,932 KB |
| testcase_48 | AC | 48 ms
11,744 KB |
コンパイルメッセージ
warning: unused variable: `i`
--> Main.rs:262:9
|
262 | for i in 0..m {
| ^ 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:275:13
|
275 | let mut x = vp.pop().unwrap();
| ----^
| |
| help: remove this `mut`
|
= note: `#[warn(unused_mut)]` on by default
warning: variable does not need to be mutable
--> Main.rs:281:9
|
281 | let mut res = djikstra(&graph, 0)[n - 1];
| ----^^^
| |
| help: remove this `mut`
warning: 3 warnings emitted
ソースコード
// -*- coding:utf-8-unix -*-
// #![feature(map_first_last)]
#![allow(dead_code)]
#![allow(unused_imports)]
#![allow(unused_macros)]
use std::collections::*;
use std::convert::*;
use std::convert::{From, Into};
use std::fmt::Debug;
use std::fs::File;
use std::io::prelude::*;
use std::io::*;
use std::marker::Copy;
use std::mem::*;
use std::ops::Bound::*;
use std::ops::{Add, Mul, Neg, Sub};
use std::str;
use std::vec;
use std::{cmp, process::Output};
use std::{cmp::Ordering, env::consts::DLL_PREFIX};
use std::{cmp::Ordering::*, f32::consts::PI};
const INF: i64 = 1223372036854775807;
const UINF: usize = INF as usize;
const FINF: f64 = 122337203685.0;
const INF128: i128 = 1223372036854775807000000000000;
const LINF: i64 = 2147483647;
// const MOD: i64 = 1000000007;
const MOD: i64 = 998244353;
const UMOD: usize = MOD as usize;
use std::cmp::*;
use std::collections::*;
use std::io::stdin;
use std::io::stdout;
use std::io::Write;
macro_rules! p {
($x:expr) => {
println!("{:?}", $x);
};
}
macro_rules! pp {
($x:expr) => {
println!("{}", $x);
};
}
// 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 readi() -> (i64) {
// let mut str = String::new();
// let _ = stdin().read_line(&mut str).unwrap();
// let mut iter = str.split_whitespace();
// iter.next().unwrap().parse::<i64>().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_vec2<T: std::str::FromStr>(n: u32) -> Vec<Vec<T>> {
(0..n).map(|_| read_vec()).collect()
}
#[allow(dead_code)]
fn readii() -> (i64, i64) {
let mut str = String::new();
let _ = stdin().read_line(&mut str).unwrap();
let mut iter = str.split_whitespace();
(
iter.next().unwrap().parse::<i64>().unwrap(),
iter.next().unwrap().parse::<i64>().unwrap(),
)
}
fn readff() -> (f64, f64) {
let mut str = String::new();
let _ = stdin().read_line(&mut str).unwrap();
let mut iter = str.split_whitespace();
(
iter.next().unwrap().parse::<f64>().unwrap(),
iter.next().unwrap().parse::<f64>().unwrap(),
)
}
#[allow(dead_code)]
fn readiii() -> (i64, i64, i64) {
let mut str = String::new();
let _ = stdin().read_line(&mut str).unwrap();
let mut iter = str.split_whitespace();
(
iter.next().unwrap().parse::<i64>().unwrap(),
iter.next().unwrap().parse::<i64>().unwrap(),
iter.next().unwrap().parse::<i64>().unwrap(),
)
}
#[allow(dead_code)]
fn readuu() -> (usize, usize) {
let mut str = String::new();
let _ = stdin().read_line(&mut str).unwrap();
let mut iter = str.split_whitespace();
(
iter.next().unwrap().parse::<usize>().unwrap(),
iter.next().unwrap().parse::<usize>().unwrap(),
)
}
fn readcc() -> (char, char) {
let mut str = String::new();
let _ = stdin().read_line(&mut str).unwrap();
let mut iter = str.split_whitespace();
(
iter.next().unwrap().parse::<char>().unwrap(),
iter.next().unwrap().parse::<char>().unwrap(),
)
}
#[allow(dead_code)]
fn readuuu() -> (usize, usize, usize) {
let mut str = String::new();
let _ = stdin().read_line(&mut str).unwrap();
let mut iter = str.split_whitespace();
(
iter.next().unwrap().parse::<usize>().unwrap(),
iter.next().unwrap().parse::<usize>().unwrap(),
iter.next().unwrap().parse::<usize>().unwrap(),
)
}
#[allow(dead_code)]
fn readuuuu() -> (usize, usize, usize, usize) {
let mut str = String::new();
let _ = stdin().read_line(&mut str).unwrap();
let mut iter = str.split_whitespace();
(
iter.next().unwrap().parse::<usize>().unwrap(),
iter.next().unwrap().parse::<usize>().unwrap(),
iter.next().unwrap().parse::<usize>().unwrap(),
iter.next().unwrap().parse::<usize>().unwrap(),
)
}
fn readiiii() -> (i64, i64, i64, i64) {
let mut str = String::new();
let _ = stdin().read_line(&mut str).unwrap();
let mut iter = str.split_whitespace();
(
iter.next().unwrap().parse::<i64>().unwrap(),
iter.next().unwrap().parse::<i64>().unwrap(),
iter.next().unwrap().parse::<i64>().unwrap(),
iter.next().unwrap().parse::<i64>().unwrap(),
)
}
pub struct Dsu {
n: usize,
// root node: -1 * component size
// otherwise: parent
parent_or_size: Vec<i32>,
}
impl Dsu {
// 0 <= size <= 10^8 is constrained.
pub fn new(size: usize) -> Self {
Self {
n: size,
parent_or_size: vec![-1; size],
}
}
pub fn merge(&mut self, a: usize, b: usize) -> usize {
assert!(a < self.n);
assert!(b < self.n);
let (mut x, mut y) = (self.leader(a), self.leader(b));
if x == y {
return x;
}
if -self.parent_or_size[x] < -self.parent_or_size[y] {
std::mem::swap(&mut x, &mut y);
}
self.parent_or_size[x] += self.parent_or_size[y];
self.parent_or_size[y] = x as i32;
x
}
pub fn same(&mut self, a: usize, b: usize) -> bool {
assert!(a < self.n);
assert!(b < self.n);
self.leader(a) == self.leader(b)
}
pub fn leader(&mut self, a: usize) -> usize {
assert!(a < self.n);
if self.parent_or_size[a] < 0 {
return a;
}
self.parent_or_size[a] = self.leader(self.parent_or_size[a] as usize) as i32;
self.parent_or_size[a] as usize
}
pub fn size(&mut self, a: usize) -> usize {
assert!(a < self.n);
let x = self.leader(a);
-self.parent_or_size[x] as usize
}
pub fn groups(&mut self) -> Vec<Vec<usize>> {
let mut leader_buf = vec![0; self.n];
let mut group_size = vec![0; self.n];
for i in 0..self.n {
leader_buf[i] = self.leader(i);
group_size[leader_buf[i]] += 1;
}
let mut result = vec![Vec::new(); self.n];
for i in 0..self.n {
result[i].reserve(group_size[i]);
}
for i in 0..self.n {
result[leader_buf[i]].push(i);
}
result
.into_iter()
.filter(|x| !x.is_empty())
.collect::<Vec<Vec<usize>>>()
}
}
fn djikstra(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 (n, m) = readuu();
let mut vp = vec![(0, 0, 0); 0];
for i in 0..m {
let (a, b, c) = readuuu();
vp.push((c, a - 1, b - 1));
}
let mut graph = vec![vec![(0 as usize, 0 as usize); (0) as usize]; (n) as usize];
vp.sort();
// vp.reverse();
let mut mi = INF as usize;
let mut uf = Dsu::new(n);
while !vp.is_empty() {
if uf.same(0, n - 1) {
break;
}
let mut x = vp.pop().unwrap();
uf.merge(x.1, x.2);
graph[x.1].push((x.2, 1));
graph[x.2].push((x.1, 1));
mi = min(mi, x.0);
}
let mut res = djikstra(&graph, 0)[n - 1];
println!("{} {}", mi, res);
return;
}
fn main() {
solve()
}