abc035d.rs

use std::collections::BinaryHeap;
use std::cmp::Ordering;
use std::cmp::max;
use std::usize;

const INF : i64 = 1000000000000000000;
#[derive(Clone)]
struct Edge {
    to : usize,
    cost : i64,
}

#[derive(Copy, Clone, Eq, PartialEq)]
struct State {
    cost : i64,
    pos : usize,
}

//https://doc.rust-lang.org/std/collections/binary_heap/ からコピペ
impl Ord for State {
    fn cmp(&self, other: &State) -> Ordering {
        other.cost.cmp(&self.cost)
    }
}
impl PartialOrd for State {
    fn partial_cmp(&self, other: &State) -> Option<Ordering> {
        Some(self.cmp(other))
    }
}

fn dijkstra(graph : &Vec<Vec<Edge>>, n : usize) -> Vec<i64> {
    let mut dist  = vec![INF; n];
    dist[0] = 0;
    let mut que = BinaryHeap::new();
    que.push(State { cost: 0, pos: 0 });
    
    while let Some(State { cost, pos }) = que.pop() {
        if cost > dist[pos] { continue; }
        for edge in &graph[pos] {
            let nxt = State { cost: cost + edge.cost, pos: edge.to };
            if nxt.cost < dist[nxt.pos] {
                que.push(nxt);
                dist[nxt.pos] = nxt.cost;
            }
        }
    }
    dist
}
fn main() {
    let (n, m, t) = {
        let temp = getvec();
        (temp[0], temp[1], temp[2])
    };
    let n = n as usize;
    let money = getvec();
    let mut graph1 = vec![vec![]; n];
    let mut graph2 = vec![vec![]; n];
    for _ in 0..m {
        let (a, b, c) = {
            let temp = getvec();
            (temp[0] - 1, temp[1] - 1, temp[2])
        };
        let a = a as usize;
        let b = b as usize;
        graph1[a].push(Edge{ to: b, cost: c });
        graph2[b].push(Edge{ to: a, cost: c });
    }
    let dist1 = dijkstra(&graph1, n);
    let dist2 = dijkstra(&graph2, n);
    let mut ans : i64 = 0;
    for i in 0..n {
        if dist1[i] == INF { continue; }
        let time : i64 = t - dist1[i] - dist2[i];
        if time > 0 {ans = max(ans, time * money[i]);}
    }
    println!("{}", ans);
}
fn next_line() -> String {
    let mut input = String::new();
    std::io::stdin().read_line(&mut input).unwrap();
    input
}

fn getvec() -> Vec<i64> {
    let res = next_line();
    let res : Vec<i64> = res.split_whitespace().map(|x| x.parse().unwrap()).collect();
    return res;
}