Submission #677106

---

Source Code Expand

use std::io;
use std::str::FromStr;
use std::cmp::{ min, max };
use std::collections::{ BinaryHeap, VecDeque };

const INF: i64 = 1_000_000_007;

type Edge = (usize, i64);
fn dij(adj: &Vec<Vec<Edge>>, s:usize) -> Vec<i64> {
    let mut dist = vec![INF; adj.len()]; dist[s] = 0;
    let mut heap = BinaryHeap::new(); heap.push((0, s));
    while let Some((_, v)) = heap.pop() {
        for edge in &adj[v] {
            let (u, cost) = *edge;
            if dist[u] > dist[v] + cost {
                dist[u] = dist[v] + cost;
                heap.push(( -dist[u] , u ));
            }
        }
    }
    dist
}

fn main() {
  let mut sc = Scanner::new();
  let n: usize = sc.cin();
  let m: usize = sc.cin();
  let t: i64 = sc.cin();

  let mut a = vec![0; n]; for i in 0..n { a[i] = sc.cin(); };
  let mut neigh = vec![vec![]; n];
  let mut reigh = vec![vec![]; n];

  for _ in 0..m {
      let x = sc.cin::<usize>() - 1;
      let y = sc.cin::<usize>() - 1;
      let c: i64 = sc.cin();
      neigh[x].push((y, c));
      reigh[y].push((x, c));
  }
  
  let dist = dij(&neigh, 0);
  let rist = dij(&reigh, 0);

  let mut ans = a[0] * t;
  for i in 1..n {
      if dist[i] == INF || rist[i] == INF { continue }
      let rest = t - dist[i] as i64 - rist[i] as i64 ;
      if rest > 0 { ans = max(ans, rest * a[i]) }
  }
  println!("{}", ans);

}

#[allow(dead_code)]
struct Scanner { stdin: io::Stdin, buffer: VecDeque<String>, }
#[allow(dead_code)]
impl Scanner {
    fn new() -> Scanner { Scanner { stdin: io::stdin(), buffer: VecDeque::new() } }
    fn reserve(&mut self) {
        while self.buffer.len() == 0 {
            let mut line = String::new();
            let _ = self.stdin.read_line(&mut line);
            for w in line.split_whitespace() {
                self.buffer.push_back(String::from(w));
            }
        }
    }
    fn cin<T: FromStr>(&mut self) -> T {
        self.reserve();
        match self.buffer.pop_front().unwrap().parse::<T>() {
            Ok(a) => a,
            Err(_) => panic!("parse err")
        }
    }
    fn get_char(&mut self) -> char {
        self.reserve();
        let head = self.buffer[0].chars().nth(0).unwrap();
        let tail = String::from( &self.buffer[0][1..] );
        if tail.len()>0 { self.buffer[0]=tail } else { self.buffer.remove(0); }
        head
    }
}

Submission Info

Compile Error

./Main.rs:3:17: 3:20 warning: unused import, #[warn(unused_imports)] on by default
./Main.rs:3 use std::cmp::{ min, max };
                            ^~~

Judge Result