Submission #63283195

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#![allow(unused_imports)]
#![allow(unused_variables)]
#![allow(non_snake_case)]
use ac_library::*;
use once_cell::sync::Lazy;
use static_assertions::*;
use varisat::*;
use memoise::*;
use argio::*;
use bitvec::prelude::*;
use counter::Counter;
use hashbag::*;
use pathfinding::prelude::*;
use recur_fn::*;
use ::indexing::*;
use amplify::*;
use amplify_derive::*;
use amplify_num::*;
use easy_ext::*;
use multimap::*;
use btreemultimap::*;
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

#![allow(unused_imports)]
#![allow(unused_variables)]
#![allow(non_snake_case)]
use ac_library::*;
use once_cell::sync::Lazy;
use static_assertions::*;
use varisat::*;
use memoise::*;
use argio::*;
use bitvec::prelude::*;
use counter::Counter;
use hashbag::*;
use pathfinding::prelude::*;
use recur_fn::*;
use ::indexing::*;
use amplify::*;
use amplify_derive::*;
use amplify_num::*;
use easy_ext::*;
use multimap::*;
use btreemultimap::*;
use bstr::*;
use az::*;
use glidesort::*;
use ::tap::*;
use omniswap::*;
use multiversion::*;
use ::num::*;
use num_bigint::*;
use num_complex::*;
use num_integer::*;
use num_iter::*;
use num_rational::*;
use num_traits::*;
use num_derive::*;
use ndarray::*;
use nalgebra::*;
use alga::*;
use libm::*;
use rand::*;
use getrandom::*;
use rand_chacha::*;
use rand_core::*;
use rand_hc::*;
use rand_pcg::*;
use rand_distr::*;
use petgraph::graph::{DiGraph, UnGraph};
use indexmap::*;
use regex::*;
use lazy_static::*;
use ordered_float::*;
use ascii::*;
use permutohedron::*;
use superslice::*;
use itertools::*;
use itertools_num::*;
use maplit::*;
use either::*;
use im_rc::*;
use fixedbitset::*;
use bitset_fixed::*;
use proconio::input;
use proconio::marker::{Bytes, Chars, Usize1};
use text_io::*;
use rustc_hash::*;
use smallvec::*;
use std::collections::{BTreeMap, BTreeSet, HashMap, HashSet, BinaryHeap};

fn main() {
    input! {
        N: usize,
        M: usize,
        X: usize,
    }

    let ans = solve(N, M, X);
    println!("{}", ans);
}

fn solve(N: usize, M: usize, X: usize) -> usize {
    input! {
        uv: [(Usize1, Usize1); M],
    }

    let mut original = DiGraph::<(), ()>::new();
    let mut reversed = DiGraph::<(), ()>::new();

    for _ in 0..N {
        original.add_node(());
        reversed.add_node(());
    }

    for &(u, v) in &uv {
        original.add_edge(original.node_indices().nth(u).unwrap(),
                          original.node_indices().nth(v).unwrap(), ());
        reversed.add_edge(reversed.node_indices().nth(v).unwrap(),
                          reversed.node_indices().nth(u).unwrap(), ());
    }

    let mut dist = vec![vec![usize::MAX; 2]; N];
    let mut queue = BinaryHeap::new();

    dist[0][0] = 0;
    queue.push(std::cmp::Reverse((0, 0, 0)));

    while let Some(std::cmp::Reverse((cost, node, state))) = queue.pop() {
        if node == N - 1 {
            return cost;
        }

        if cost > dist[node][state] {
            continue;
        }

        let cur = if state == 0 { &original } else { &reversed };
        let node_i = cur.node_indices().nth(node).unwrap();

        for neighbor in cur.neighbors(node_i) {
            let next_node = neighbor.index();
            let next_cost = cost + 1;

            if next_cost < dist[next_node][state] {
                dist[next_node][state] = next_cost;
                queue.push(std::cmp::Reverse((next_cost, next_node, state)));
            }
        }

        let next_state = 1 - state;
        let next_cost = cost + X;

        if next_cost < dist[node][next_state] {
            dist[node][next_state] = next_cost;
            queue.push(std::cmp::Reverse((next_cost, node, next_state)));
        }
    }
    unreachable!();
}

Submission Info

Judge Result