Submission #731407

---

Source Code Expand

import java.io.*;
import java.util.*;
public class Main {
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	public static void main(String[] args) throws IOException{
		MyScanner sc = new MyScanner();
		PriorityQueue<Vertex> que = new PriorityQueue<>();
		int N = sc.nextInt(), M =sc.nextInt(), T = sc.nextInt();
		ArrayList<Edge> es[] = new ArrayList[N+1];
		ArrayList<Edge> es2[] = new ArrayList[N+1];
		
		int[] A = new int[N+1];
		for (int i = 1; i <= N; i++){
			A[i] = sc.nextInt();
			es[i] = new ArrayList<Edge>();
			es2[i] = new ArrayList<Edge>();
		}

//		input edges
		int a, b, c;
		for (int i = 0; i < M; i++){
			a = sc.nextInt();
			b = sc.nextInt();
			c = sc.nextInt();
			es[a].add(new Edge(b,(long)c));
			es2[b].add(new Edge(a,(long)c));
		}
	
		long max = A[1] * T;
		if (N==1){
			System.out.println(max);
			return;
		}
		
//		go!
		long shortest_go[] = dijkstra(N, es, 1);
//		back!
		long shortest_back[] = dijkstra(N, es2, 1);
		long this_cost;
//		calculate the treature		
		for (int i = 2; i <=N; i++){
			this_cost = (T - shortest_go[i] - shortest_back[i]) * A[i];
			if (this_cost > max)
				max = this_cost;
		}

		System.out.println(max);
		
	}
	
	static long[] dijkstra(int N, ArrayList<Edge> es[], int start){
		PriorityQueue<Vertex> pq = new PriorityQueue<>();
		long[] shortest = new long[N+1];
		Arrays.fill(shortest, Long.MAX_VALUE);
		shortest[start] = 0;

		pq.add(new Vertex(start, 0));
		while(!pq.isEmpty()){
			Vertex v = pq.poll();
			for (Edge e : es[v.no]){
				long d = e.dist + v.dist;
				if (d < shortest[e.to]){
					shortest[e.to] = d;
					pq.add(new Vertex(e.to, d));
				}
			}
		}

		return shortest;
	}
	
	static void debug(Object... o) {
		System.out.println(Arrays.deepToString(o));
	}
	
	static class Vertex implements Comparable<Vertex>{
		int no;
		long dist;
		Vertex (int no, long dist){
			this.no = no;
			this.dist = dist;
		}
		@Override
		public int compareTo(Vertex o) {
			if (this.dist - o.dist > 0)
				return 1;
			else
				return 0;
		}
	}

	static class Edge{
		int to;
		long dist;
		Edge(int to, long dist){
			this.to = to;
			this.dist = dist;
		}
	}

	static class MyScanner {
		int nextInt() {
			try {
				int c = System.in.read();
				while (c != '-' && (c < '0' || '9' < c))
					c = System.in.read();
				if (c == '-')
					return -nextInt();
				int res = 0;
				do {
					res *= 10;
					res += c - '0';
					c = System.in.read();
				} while ('0' <= c && c <= '9');
				return res;
			} catch (Exception e) {
				return -1;
			}
		}
		double nextDouble() {
			return Double.parseDouble(next());
		}

		long nextLong() {
			return Long.parseLong(next());
		}

		String next() {
			try {
				StringBuilder res = new StringBuilder("");
				int c = System.in.read();
				while (Character.isWhitespace(c))
					c = System.in.read();
				do {
					res.append((char) c);
				} while (!Character.isWhitespace(c = System.in.read()));
				return res.toString();
			} catch (Exception e) {
				return null;
			}
		}
	}
	
}

Submission Info

Compile Error

Note: ./Main.java uses unchecked or unsafe operations.
Note: Recompile with -Xlint:unchecked for details.

Judge Result