#293275 (Rust) No.20 砂漠のオアシス

• 問題: No.20 砂漠のオアシス
• ユーザー: sntea
• 提出日時: 2018-10-20 01:35:31
• 言語: Rust (1.77.0 + proconio)
• 結果: AC
• 実行時間: 20 ms / 5,000 ms
• コード長: 11,271 bytes
• コンパイル時間: 13,575 ms
• コンパイル使用メモリ: 386,456 KB
• 実行使用メモリ: 7,232 KB
• 最終ジャッジ日時: 2024-11-19 00:37:47
• 合計ジャッジ時間: 14,394 ms
• ジャッジサーバーID （参考情報）: judge5 / judge4

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	1 ms; 6,816 KB
testcase_01	AC	1 ms; 6,816 KB
testcase_02	AC	1 ms; 6,820 KB
testcase_03	AC	1 ms; 6,816 KB
testcase_04	AC	2 ms; 6,816 KB
testcase_05	AC	19 ms; 6,820 KB
testcase_06	AC	20 ms; 7,224 KB
testcase_07	AC	19 ms; 7,232 KB
testcase_08	AC	19 ms; 7,228 KB
testcase_09	AC	18 ms; 7,224 KB
testcase_10	AC	0 ms; 6,816 KB
testcase_11	AC	1 ms; 6,816 KB
testcase_12	AC	1 ms; 6,816 KB
testcase_13	AC	2 ms; 6,816 KB
testcase_14	AC	3 ms; 6,816 KB
testcase_15	AC	2 ms; 6,820 KB
testcase_16	AC	4 ms; 6,816 KB
testcase_17	AC	3 ms; 6,816 KB
testcase_18	AC	3 ms; 6,820 KB
testcase_19	AC	4 ms; 6,816 KB
testcase_20	AC	1 ms; 6,820 KB

コンパイルメッセージ

warning: unused variable: `from`
   --> src/main.rs:294:39
    |
294 |     fn get_shortest_path_graph(&self, from: usize, dist: &Vec<Self::Cost>) -> AdjList<Self::Cost> {
    |                                       ^^^^ help: if this is intentional, prefix it with an underscore: `_from`
    |
    = note: `#[warn(unused_variables)]` on by default

warning: variable does not need to be mutable
   --> src/main.rs:9:13
    |
9   |           let mut s = {
    |               ----^
    |               |
    |               help: remove this `mut`
...
378 | /     input! {
379 | |         n: usize,
380 | |         v: i64,
381 | |         ox: usize,
382 | |         oy: usize,
383 | |         l: [[i64; n]; n],
384 | |     }
    | |_____- in this macro invocation
    |
    = note: `#[warn(unused_mut)]` on by default
    = note: this warning originates in the macro `input` (in Nightly builds, run with -Z macro-backtrace for more info)

warning: method `add_uedge` is never used
   --> src/main.rs:155:8
    |
141 | impl<Cost: Clone> AdjList<Cost> {
    | ------------------------------- method in this implementation
...
155 |     fn add_uedge(&mut self, from: usize, to_: usize, cost_: Cost) {
    |        ^^^^^^^^^
    |
    = note: `#[warn(dead_code)]` on by default

warning: method `vizualize` is never used
   --> src/main.rs:310:8
    |
309 | impl<Cost: Clone> AdjList<Cost> {
    | ------------------------------- method in this implementation
310 |     fn vizualize(&self, name: &str) {
    |        ^^^^^^^^^

warning: method `viz_with_cost` is never used
   --> src/main.rs:340:8
    |
339 | impl<Cost: Clone + std::fmt::Display> AdjList<Cost> {
    | --------------------------------------------------- method in this implementation
340 |     fn viz_with_cost(&self, name: &str) {
    |        ^^^^^^^^^^^^^

warning: unused `Result` that must be used
   --> src/main.rs:320:17
    |
320 |                 writeln!(&mut out, "    {}[];", p);
    |                 ^^^^^^^^^^^^^^^^^^^^^

ソースコード

// from https://qiita.com/tanakh/items/0ba42c7ca36cd29d0ac8
#[allow(unused_macros)]
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
    ($($r:tt)*) => {
        let mut s = {
            use std::io::Read;
            let mut s = String::new();
            std::io::stdin().read_to_string(&mut s).unwrap();
            s
        };
        let mut iter = s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
}

#[allow(unused_macros)]
macro_rules! input_inner {
    ($iter:expr) => {};
    ($iter:expr, ) => {};

    ($iter:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($iter, $t);
        input_inner!{$iter $($r)*}
    };
}

#[allow(unused_macros)]
macro_rules! read_value {
    ($iter:expr, ( $($t:tt),* )) => {
        ( $(read_value!($iter, $t)),* )
    };

    ($iter:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($iter, $t)).collect::<Vec<_>>()
    };

    ($iter:expr, chars) => {
        read_value!($iter, String).chars().collect::<Vec<char>>()
    };

    ($iter:expr, usize1) => {
        read_value!($iter, usize) - 1
    };

    ($iter:expr, $t:ty) => {
        $iter.next().unwrap().parse::<$t>().expect("Parse error")
    };
}

#[allow(unused_macros)]
macro_rules! debug {
    ($x: expr) => {
        println!("{}: {:?}", stringify!($x), $x)
    };
}
// macro_rules! debug { ($x: expr) => () }

#[allow(dead_code)]
fn show<T>(iter: T) -> String
where
    T: Iterator,
    T::Item: std::fmt::Display,
{
    let mut res = iter.fold(String::new(), |sum, e| sum + &format!("{} ", e));
    res.pop();
    res
}

#[allow(unused_imports)]
use std::cmp::{max, min};
#[allow(unused_imports)]
use std::collections::btree_map::Entry::{Occupied, Vacant};
#[allow(unused_imports)]
use std::collections::{BTreeMap, BTreeSet, BinaryHeap, HashMap, HashSet, VecDeque};
#[allow(unused_imports)]
use std::mem::swap;

use std::clone::Clone;
use std::cmp::Ordering;
#[derive(Clone, Debug, Hash, Eq, PartialEq)]
struct Edge<Cost>
where
    Cost: std::clone::Clone,
{
    to: usize,
    cost: Cost,
}

impl<Cost> Ord for Edge<Cost>
where
    Cost: Ord + std::clone::Clone,
{
    fn cmp(&self, other: &Edge<Cost>) -> Ordering {
        (self.cost).cmp(&(other.cost)).reverse()
    }
}

impl<Cost> PartialOrd for Edge<Cost>
where
    Cost: std::clone::Clone,
    Edge<Cost>: Ord,
{
    fn partial_cmp(&self, other: &Edge<Cost>) -> Option<std::cmp::Ordering> {
        Some(self.cmp(other))
    }
}

trait Graph
where
    Self::Cost: Clone,
{
    type Cost;
    fn len(&self) -> usize;
    fn get<'a>(&'a self, p: usize) -> std::slice::Iter<'a, Edge<Self::Cost>>;
    fn get_order(&self) -> Vec<usize>;
}

#[derive(Clone, Debug, Hash)]
struct AdjList<Cost: Clone> {
    adj: Vec<Vec<Edge<Cost>>>,
}

impl<Cost: Clone> std::ops::Index<usize> for AdjList<Cost> {
    type Output = Vec<Edge<Cost>>;

    fn index(&self, i: usize) -> &Vec<Edge<Cost>> {
        &self.adj[i]
    }
}

impl<Cost: Clone> std::ops::IndexMut<usize> for AdjList<Cost> {
    fn index_mut<'a>(&'a mut self, i: usize) -> &'a mut Vec<Edge<Cost>> {
        &mut self.adj[i]
    }
}

impl<Cost: Clone> AdjList<Cost> {
    fn new(n: usize) -> AdjList<Cost> {
        AdjList {
            adj: vec![vec![]; n],
        }
    }

    fn add_edge(&mut self, from: usize, to_: usize, cost_: Cost) {
        self.adj[from].push(Edge {
            to: to_,
            cost: cost_,
        });
    }

    fn add_uedge(&mut self, from: usize, to_: usize, cost_: Cost) {
        self.add_edge(from, to_, cost_.clone());
        self.add_edge(to_, from, cost_);
    }
}

impl<Cost> Graph for AdjList<Cost>
where
    Cost: Clone,
{
    type Cost = Cost;

    fn len(&self) -> usize {
        self.adj.len()
    }

    fn get<'a>(&'a self, p: usize) -> std::slice::Iter<'a, Edge<Cost>> {
        self.adj[p].iter()
    }

    fn get_order(&self) -> Vec<usize> {
        let mut res = Vec::with_capacity(self.len());
        let mut deg = vec![0; self.len()];
        let mut used = vec![false; self.len()];
        for from in 0..self.len() {
            for e in self.get(from) {
                deg[e.to] += 1;
            }
        }
        for s in 0..self.len() {
            if deg[s] != 0 || used[s] {
                continue;
            }
            let mut stack = Vec::new();
            used[s] = true;
            stack.push(s);
            while let Some(p) = stack.pop() {
                used[p] = true;
                res.push(p);
                for e in self.get(p) {
                    deg[e.to] -= 1;
                    if deg[e.to] == 0 {
                        stack.push(e.to);
                    }
                }
            }
        }
        // debug!(deg);
        res
    }
}

// --------------------

trait Zero {
    fn zero() -> Self;
}

impl Zero for i64 {
    fn zero() -> i64 {
        0
    }
}

trait Max {
    fn max_value() -> Self;
}

impl Max for i64 {
    fn max_value() -> i64 {
        std::i64::MAX
    }
}

trait GraphHavingOrderedCost: Graph
where
    Self::Cost: Ord + Add<Self::Cost, Output = Self::Cost> + Zero + Max + Copy,
{
    fn get_shortest_path(&self, from: usize) -> (Vec<Self::Cost>, Vec<usize>);
    fn bellmanford(&self, from: usize) -> (Vec<Self::Cost>, Vec<bool>);
    fn get_shortest_path_graph(&self, from: usize, dist: &Vec<Self::Cost>) -> AdjList<Self::Cost>;
}

use std::ops::Add;
impl<T> GraphHavingOrderedCost for T
where
    T: Graph,
    T::Cost: Ord + Add<T::Cost, Output = T::Cost> + Zero + Max + Copy,
    Edge<T::Cost>: Ord,
{
    fn get_shortest_path(&self, from: usize) -> (Vec<Self::Cost>, Vec<usize>) {
        let n = self.len();

        let mut dist = vec![Self::Cost::max_value(); n];
        let mut pre = vec![n as usize; n];
        let mut heap = std::collections::BinaryHeap::new();
        heap.push(Edge {
            to: from,
            cost: Self::Cost::zero(),
        });
        dist[from] = Self::Cost::zero();
        while let Some(p) = heap.pop() {
            for e in self.get(p.to) {
                if p.cost + e.cost >= dist[e.to] {
                    continue;
                }
                heap.push(Edge {
                    to: e.to,
                    cost: p.cost + e.cost,
                });
                dist[e.to] = p.cost + e.cost;
                pre[e.to] = p.to;
            }
        }
        (dist, pre)
    }

    fn bellmanford(&self, from: usize) -> (Vec<Self::Cost>, Vec<bool>) {
        let n = self.len();
        let mut dist = vec![Self::Cost::max_value(); n];
        let mut updated = vec![true; n];
        dist[from] = Self::Cost::zero();
        for _ in 0..n + 1 {
            updated = vec![false; n];
            for from in 0..n {
                if dist[from] == Self::Cost::max_value() {
                    continue;
                }
                for e in self.get(from) {
                    if dist[e.to] > dist[from] + e.cost {
                        dist[e.to] = dist[from] + e.cost;
                        updated[e.to] = true;
                    }
                }
            }
        }
        (dist, updated)
    }

    fn get_shortest_path_graph(&self, from: usize, dist: &Vec<Self::Cost>) -> AdjList<Self::Cost> {
        let n = self.len();

        let mut res = AdjList::new(n);
        for from in 0..n {
            for e in self.get(from) {
                if dist[from] + e.cost == dist[e.to] {
                    res.add_edge(from, e.to, e.cost);
                }
            }
        }
        res
    }
}

impl<Cost: Clone> AdjList<Cost> {
    fn vizualize(&self, name: &str) {
        let path = std::path::Path::new("tmp.dot");
        {
            use std::io::{BufWriter, Write};

            let file = std::fs::File::create(path).unwrap();
            let mut out = BufWriter::new(file);
            let n = self.len();
            writeln!(&mut out, "digraph graph_name {{").unwrap();
            for p in 0..n {
                writeln!(&mut out, "    {}[];", p);
            }
            for p in 0..n {
                for e in &self[p] {
                    writeln!(&mut out, "    {} -> {}", p, e.to);
                }
            }
            writeln!(&mut out, "}}");
        }
        let mut cmd = std::process::Command::new("dot");
        cmd.arg("-T");
        cmd.arg("png");
        cmd.arg("tmp.dot");
        cmd.arg("-o");
        cmd.arg(name);
        cmd.status().expect("failed to execute dot");
    }
}

impl<Cost: Clone + std::fmt::Display> AdjList<Cost> {
    fn viz_with_cost(&self, name: &str) {
        let path = std::path::Path::new("tmp.dot");
        {
            use std::io::{BufWriter, Write};

            let file = std::fs::File::create(path).unwrap();
            let mut out = BufWriter::new(file);
            let n = self.len();
            writeln!(&mut out, "digraph graph_name {{").unwrap();
            for p in 0..n {
                writeln!(&mut out, "    {}[];", p);
            }
            for p in 0..n {
                for e in &self[p] {
                    writeln!(&mut out, "    {} -> {} [label={}]", p, e.to, e.cost);
                }
            }
            writeln!(&mut out, "}}");
        }
        let mut cmd = std::process::Command::new("dot");
        cmd.arg("-T");
        cmd.arg("png");
        cmd.arg("tmp.dot");
        cmd.arg("-o");
        cmd.arg(name);
        cmd.status().expect("failed to execute dot");
    }
}

fn main() {
    use std::io::Write;
    let out = std::io::stdout();
    let mut out = std::io::BufWriter::new(out.lock());
    #[allow(unused_macros)]
    macro_rules! printf { ($($arg:tt)*) => (write!(out, $($arg)*).unwrap()); }
    #[allow(unused_macros)]
    macro_rules! printfln { () => (writeln!(out).unwrap()); ($($arg:tt)*) => (writeln!(out, $($arg)*).unwrap()); }

    input! {
        n: usize,
        v: i64,
        ox: usize,
        oy: usize,
        l: [[i64; n]; n],
    }

    // let v = v - l[0][0];

    let dx = [0, -1, 0, 1];
    let dy = [-1, 0, 1, 0];

    let mut g = AdjList::new(n * n);
    let get_idx = |i, j| i * n + j;
    for i in 0..n {
        for j in 0..n {
            for k in 0..4 {
                let ni = i as i64 + dx[k];
                let nj = j as i64 + dy[k];
                if 0 <= ni && ni < n as i64 && 0 <= nj && nj < n as i64 {
                    let ni = ni as usize;
                    let nj = nj as usize;
                    g.add_edge(get_idx(i, j), get_idx(ni, nj), l[ni][nj]);
                }
            }
        }
    }

    let mut ans = false;
    let (dist0, _) = g.get_shortest_path(get_idx(0, 0));
    // debug!(v - dist0[get_idx(n - 1, n - 1)]);
    if v - dist0[get_idx(n - 1, n - 1)] > 0 {
        ans = true;
    }

    if ox != 0 {
        let ox = ox - 1;
        let oy = oy - 1;
        let (dist1, _) = g.get_shortest_path(get_idx(oy, ox));
        // debug!((v - dist0[get_idx(ox, oy)]) * 2 - dist1[get_idx(n - 1, n - 1)]);
        if (v - dist0[get_idx(oy, ox)]) * 2 - dist1[get_idx(n - 1, n - 1)] > 0 {
            ans = true;
        }
    }
    if ans {
        printfln!("YES");
    } else {
        printfln!("NO");
    }

    // fn dfs(x: usize, y: usize, )
}