AtCoder Beginner Contest 342 E

https://atcoder.jp/contests/abc342/tasks/abc342_e

逆から考えれば単なるダイクストラです。

// Square Pair
#![allow(non_snake_case)]

use std::cmp::min;


//////////////////// 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()
}


//////////////////// TimeTable ////////////////////

type Time = i64;
type Node = usize;

#[derive(Clone)]
struct TimeTable {
    l: Time,
    d: Time,
    k: Time,
    c: Time,
    A: Node,
    B: Node
}

impl TimeTable {
    fn latest_start_time(&self, t0: Time) -> Option<Time> {
        if t0 < self.c + self.l + self.d {
            None
        }
        else {
            let i = min(self.k-1, (t0 - self.c - self.l) / self.d);
            Some(self.l + i * self.d)
        }
    }
    
    fn read() -> TimeTable {
        let v = read_vec();
        let (l, d, k, c) = (v[0], v[1], v[2], v[3]);
        let (A, B) = ((v[4] - 1) as Node, (v[5] - 1) as Node);
        TimeTable { l, d, k, c, A, B }
    }
}


//////////////////// Graph ////////////////////

struct Graph {
    vs: Vec<Vec<TimeTable>>
}

impl Graph {
    fn neighbors(&self, v0: Node, t0: Time) -> Vec<(Node, Time)> {
        let mut neighs: Vec<(Node, Time)> = vec![];
        for timetable in self.vs[v0].iter() {
            if let Some(t) = timetable.latest_start_time(t0) {
                neighs.push((timetable.A, t))
            }
        }
        neighs
    }
    
    fn create(N: usize, timetables: Vec<TimeTable>) -> Graph {
        let mut vs: Vec<Vec<TimeTable>> = vec![vec![]; N];
        for time in timetables.into_iter() {
            vs[time.B].push(time)
        }
        Graph { vs }
    }
}


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

const INF: Time = 10_i64.pow(18)*2;

use std::collections::BinaryHeap;

#[derive(Debug, Eq, PartialEq)]
struct Item {
    time: Time,
    node: Node,
}

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

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

fn Dijkstra(graph: Graph, v0: Node) -> Vec<Time> {
    let N = graph.vs.len();
    let mut times: Vec<Time> = vec![0; N];
    let mut heap = BinaryHeap::new();
    heap.push(Item { time: INF, node: v0 });
    while let Some(v) = heap.pop() {
        if times[v.node] != 0 {
            continue
        }
        
        times[v.node] = v.time;
        let neis = graph.neighbors(v.node, v.time);
        for (v2, t2) in neis.into_iter() {
            if times[v2] == 0 {
                heap.push(Item { time: t2, node: v2 })
            }
        }
    }
    times
}


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

fn read_input() -> (usize, Vec<TimeTable>) {
    let v = read_vec();
    let (N, M) = (v[0], v[1]);
    let timetables = (0..M).map(|_| TimeTable::read()).collect::<Vec<_>>();
    (N, timetables)
}

fn F(N: usize, timetables: Vec<TimeTable>) {
    let graph = Graph::create(N, timetables);
    let times = Dijkstra(graph, N-1);
    for i in 0..N-1 {
        if times[i] != 0 {
            println!("{}", times[i])
        }
        else {
            println!("Unreachable")
        }
    }
}

fn main() {
    let (N, timetables) = read_input();
    F(N, timetables)
}