As Soon As Possible 2

#![allow(non_snake_case)]

​

#[fastout]

fn main() {

  input! {

    N: usize, M: usize, Q: usize,

    edges: [(Usize1, Usize1, i64); M],

    h: [Usize1; Q],

  }

​

  let mut graph_backward = vec![vec![]; N];

  let mut graph_forward = vec![vec![]; N];

  for (A, B, C) in edges {

    graph_backward[B].push((A, C));

    graph_forward[A].push((B, C));

  }

​

  let mut dist_backward = dijkstra(&graph_backward, 0);

  let mut dist_forward = dijkstra(&graph_forward, 0);

​

  for i in h {

    println!("{}", dist_backward[i] + dist_forward[i]);

  }

}

​

fn dijkstra(graph: &Vec<Vec<(usize, i64)>>, start: usize) -> Vec<i64> {

  let mut dist = vec![INF; graph.len()];

  dist[start] = 0;

  let mut pq = BinaryHeap::new();

  pq.push((Reverse(0), start));

  while let Some((Reverse(d), u)) = pq.pop() {

    if dist[u] != d { continue }

    for &(v, c) in &graph[u] {

      if dist[v] <= d + c { continue }

      dist[v] = d + c;

      pq.push((Reverse(d + c), v));

    }

  }

  dist

}

​

const INF: i64 = 1_000_000_000_000_000_000;

​

use proconio::{input, fastout, marker::Usize1};

use std::collections::BinaryHeap;

use std::cmp::Reverse;