AtCoder Beginner Contest 395 E

https://atcoder.jp/contests/abc395/tasks/abc395_e

ただのダイクストラです。ただし、今がどちらのグラフなのかわからないといけないので、状態はノードとどちらのグラフかで、隣の状態は、そのグラフで一歩進むかグラフを反転するかです。

// Flip Edge
#![allow(non_snake_case)]


//////////////////// library ////////////////////

fn read<T: std::str::FromStr>() -> T {
    let mut line = String::new();
    std::io::stdin().read_line(&mut line).ok();
    line.trim().parse().ok().unwrap()
}

fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read::<String>().split_whitespace()
            .map(|e| e.parse().ok().unwrap()).collect()
}


//////////////////// DirectedGraph ////////////////////

type Node = usize;
type Edge = (Node, Node);
type Weight = i64;

struct DirectedGraph {
    g: Vec<Vec<Node>>
}

impl DirectedGraph {
    fn neighbors(&self, v: Node) -> Vec<Node> {
        self.g[v].clone()
    }
    
    fn inverse(&self) -> DirectedGraph {
        let N = self.g.len();
        let mut g: Vec<Vec<Node>> = vec![vec![]; N];
        for i in 0..N {
            for &j in self.g[i].iter() {
                g[j].push(i)
            }
        }
        DirectedGraph { g }
    }
    
    fn create(N: usize, edges: &Vec<Edge>) -> DirectedGraph {
        let mut g: Vec<Vec<Node>> = vec![vec![]; N];
        for &(u, v) in edges.iter() {
            g[u].push(v)
        }
        DirectedGraph { g }
    }
}


//////////////////// Dijkstra ////////////////////

use std::collections::{HashMap, BinaryHeap};

#[derive(Debug, Eq, PartialEq)]
struct Item {
    weight: Weight,
    node: Node,
    direction: bool
}

impl Item {
    fn new(w: Weight, v: Node, d: bool) -> Item {
        Item { weight: w, node: v, direction: d }
    }
}

impl Ord for Item {
    fn cmp(&self, other: &Self) -> std::cmp::Ordering {
        other.weight.cmp(&self.weight)
    }
}

impl PartialOrd for Item {
    fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
        Some(self.cmp(other))
    }
}

fn Dijkstra(graph1: DirectedGraph, graph2: DirectedGraph, X: Weight) -> Weight {
    let N = graph1.g.len();
    let mut weights: HashMap<(Node, bool), Weight> = HashMap::new();
    let mut heap = BinaryHeap::new();
    heap.push(Item { weight: 0, node: 0, direction: true });
    while let Some(v) = heap.pop() {
        if v.node == N - 1 {
            return v.weight
        }
        if weights.contains_key(&(v.node, v.direction)) {
            continue
        }
        
        weights.insert((v.node, v.direction), v.weight);
        let cur_graph = if v.direction { &graph1 } else { &graph2 };
        let neis = cur_graph.neighbors(v.node);
        for node in neis.into_iter() {
            if !weights.contains_key(&(node, v.direction)) {
                heap.push(Item::new(v.weight + 1, node, v.direction))
            }
        }
        if !weights.contains_key(&(v.node, !v.direction)) {
            heap.push(Item::new(v.weight + X, v.node, !v.direction))
        }
    }
    -1
}


//////////////////// process ////////////////////

fn read_input() -> (usize, Vec<Edge>, i64) {
    let v: Vec<usize> = read_vec();
    let (N, M, X) = (v[0], v[1], v[2] as i64);
    let edges: Vec<Edge> = (0..M).map(|_| read_edge()).collect();
    (N, edges, X)
}

fn read_edge() -> Edge {
    let v: Vec<Node> = read_vec();
    (v[0]-1, v[1]-1)
}

fn F(N: usize, edges: Vec<Edge>, X: i64) -> i64 {
    let graph = DirectedGraph::create(N, &edges);
    let inv_graph = graph.inverse();
    Dijkstra(graph, inv_graph, X)
}

fn main() {
    let (N, edges, X) = read_input();
    println!("{}", F(N, edges, X))
}