#646538 (Rust) No.1473 おでぶなおばけさん

提出ソース

結果

問題	No.1473 おでぶなおばけさん
ユーザー	Moss_Local
提出日時	2021-04-09 22:50:24
言語	Rust (1.77.0)
結果	AC
実行時間	91 ms / 2,000 ms
コード長	8,119 bytes
コンパイル時間	1,291 ms
コンパイル使用メモリ	153,264 KB
実行使用メモリ	15,808 KB
最終ジャッジ日時	2023-09-07 12:27:41
合計ジャッジ時間	6,140 ms
ジャッジサーバーID （参考情報）	judge12 / judge11

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	0 ms 4,376 KB
testcase_01	AC	1 ms 4,380 KB
testcase_02	AC	72 ms 14,520 KB
testcase_03	AC	47 ms 11,780 KB
testcase_04	AC	36 ms 9,128 KB
testcase_05	AC	12 ms 4,376 KB
testcase_06	AC	53 ms 11,588 KB
testcase_07	AC	71 ms 15,600 KB
testcase_08	AC	91 ms 15,808 KB
testcase_09	AC	79 ms 15,564 KB
testcase_10	AC	31 ms 5,268 KB
testcase_11	AC	31 ms 5,192 KB
testcase_12	AC	31 ms 5,264 KB
testcase_13	AC	20 ms 4,380 KB
testcase_14	AC	14 ms 4,380 KB
testcase_15	AC	29 ms 5,180 KB
testcase_16	AC	31 ms 5,248 KB
testcase_17	AC	2 ms 4,380 KB
testcase_18	AC	4 ms 4,380 KB
testcase_19	AC	26 ms 5,216 KB
testcase_20	AC	43 ms 10,488 KB
testcase_21	AC	43 ms 7,504 KB
testcase_22	AC	63 ms 12,916 KB
testcase_23	AC	61 ms 12,212 KB
testcase_24	AC	56 ms 11,152 KB
testcase_25	AC	65 ms 12,428 KB
testcase_26	AC	68 ms 12,224 KB
testcase_27	AC	21 ms 5,792 KB
testcase_28	AC	70 ms 15,224 KB
testcase_29	AC	36 ms 7,736 KB
testcase_30	AC	45 ms 8,748 KB
testcase_31	AC	78 ms 15,120 KB
testcase_32	AC	41 ms 11,600 KB
testcase_33	AC	38 ms 10,140 KB
testcase_34	AC	21 ms 6,472 KB
testcase_35	AC	17 ms 5,468 KB
testcase_36	AC	43 ms 9,044 KB
testcase_37	AC	56 ms 11,468 KB
testcase_38	AC	10 ms 4,384 KB
testcase_39	AC	31 ms 5,348 KB
testcase_40	AC	30 ms 5,336 KB
testcase_41	AC	31 ms 5,252 KB
testcase_42	AC	29 ms 5,256 KB
testcase_43	AC	35 ms 11,452 KB
testcase_44	AC	36 ms 11,452 KB
testcase_45	AC	37 ms 11,444 KB
testcase_46	AC	46 ms 10,328 KB
testcase_47	AC	66 ms 12,008 KB
testcase_48	AC	54 ms 11,736 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:276:13
    |
276 |         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:283:17
    |
283 |             let mut la = *vp.last().unwrap();
    |                 ----^^
    |                 |
    |                 help: remove this `mut`

warning: variable does not need to be mutable
   --> Main.rs:289:9
    |
289 |     let mut res = djikstra(&graph, 0)[n - 1];
    |         ----^^^
    |         |
    |         help: remove this `mut`

warning: 4 warnings emitted

ソースコード

raw source code

// -*- 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);
    let mut flg = false;
    while !vp.is_empty() {
        if uf.same(0, n - 1) && !flg {
            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);
        flg = false;
        if !vp.is_empty() {
            let mut la = *vp.last().unwrap();
            if la.0 == x.0 {
                flg = true;
            }
        }
    }
    let mut res = djikstra(&graph, 0)[n - 1];
    println!("{} {}", mi, res);
    return;
}

fn main() {
    solve()
}

yukicoder

結果

テストケース

コンパイルメッセージ

ソースコード