Sadonkorjuu

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

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;

class E4301 {

	static final int K = 1000;
	static int N;
	static int ANS;

	public static void main(String[] args) {
		FastReader reader = new FastReader();
		PrintWriter writer = new PrintWriter(new OutputStreamWriter(System.out));

		N = reader.nextInt();

		final List<Integer> ports = new ArrayList<>();
		final List<Pair<Integer, Integer>> connections[] = new List[N + 1];
		Arrays.fill(connections, new ArrayList<Pair<Integer, Integer>>());

		for (int i = 0; i < N; i++) {
			if (reader.nextInt() == 0)
				ports.add(i);
		}

		for (int i = 0; i < N - 1; i++) {
			int a, b, c;
			a = reader.nextInt();
			b = reader.nextInt();
			c = reader.nextInt();
			connections[a].add(new Pair<Integer, Integer>(b, c));
			connections[b].add(new Pair<Integer, Integer>(a, c));
		}

		reader.close();
		
		for (int port : ports) {
			connections[N].add(new Pair<Integer, Integer>(port, 0));
		}

		int[] distance = new int[N + 1];
		int[] visited = new int[N + 1];
		Arrays.fill(distance, 1001);
		Arrays.fill(visited, 0);

		Queue<Integer> bfs[] = new LinkedList[K + 1];
		Arrays.fill(bfs, new LinkedList<Integer>());
		bfs[0].add(N);
		distance[N] = 0;

		int pos = 0;
		int high = 1;

		while (high > 0) {

			int index = pos % K + 1;
			while (bfs[index].isEmpty()) {
				pos++;
			}

			int u = bfs[index].remove();
			high -= 1;

			if (visited[u] != 0)
				continue;
			visited[u] = 1;

			for (Pair<Integer, Integer> edge : connections[u]) {
				int cost = edge.second;
				int w = edge.first;
				if (distance[u] + cost < distance[w]) {
					if (distance[w] == K + 1) {
						ANS += distance[u] + cost;
					} else {
						ANS -= distance[w];
						ANS += distance[u] + cost;
					}

					distance[w] = distance[u] + cost;
					bfs[distance[w] % (K + 1)].add(w);
					high++;
				}

			}
		}
		
		writer.println(ANS);
		writer.flush();
		writer.close();
	}

	static class Pair<K, V> {
		K first;
		V second;

		public Pair(K first, V second) {
			this.first = first;
			this.second = second;
		}
	}

	static class FastReader {

		private BufferedReader br;
		private StringTokenizer st;

		public FastReader() {
			br = new BufferedReader(new InputStreamReader(System.in));
		}

		void close() {
			try {
				br.close();
			} catch (IOException e) {
				e.printStackTrace();
			}
			st = null;
			br = null;
		}

		String next() {
			while (st == null || !st.hasMoreElements()) {
				try {
					st = new StringTokenizer(br.readLine());
				} catch (IOException e) {
					e.printStackTrace();
				}
			}
			return st.nextToken();
		}

		String nextLine() {
			String str = "";

			try {
				str = br.readLine();
			} catch (IOException e) {
				e.printStackTrace();
			}

			return str;
		}

		int nextInt() {
			return Integer.parseInt(next());
		}

		BigInteger nextBigInteger() {
			return new BigInteger(next());
		}

		double nextDouble() {
			return Double.parseDouble(next());
		}

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

	}

}

Test 1

Group: 1, 2

Verdict: ACCEPTED

Test 2

Group: 1, 2

Verdict: ACCEPTED

Test 3

Group: 1, 2

Verdict: WRONG ANSWER

Test 4

Group: 1, 2

Verdict: WRONG ANSWER

Test 5

Group: 1, 2

Verdict: ACCEPTED

Test 6

Group: 1, 2

Verdict: WRONG ANSWER

Test 7

Group: 2

Verdict: TIME LIMIT EXCEEDED

Test 8

Group: 1, 2

Verdict: WRONG ANSWER

Test 9

Group: 2

Verdict: TIME LIMIT EXCEEDED

Test 10

Group: 1, 2

Verdict: WRONG ANSWER

Test 11

Group: 2

Verdict: TIME LIMIT EXCEEDED

Test 12

Group: 2

Verdict: TIME LIMIT EXCEEDED

Test 13

Group: 2

Verdict: TIME LIMIT EXCEEDED

Test 14

Group: 2

Verdict: TIME LIMIT EXCEEDED

Test 15

Group: 1, 2

Verdict: WRONG ANSWER

Test 16

Group: 1, 2

Verdict: WRONG ANSWER

Test 17

Group: 1, 2

Verdict: WRONG ANSWER

Test 18

Group: 1, 2

Verdict: WRONG ANSWER

Test 19

Group: 1, 2

Verdict: WRONG ANSWER

Test 20

Group: 1, 2

Verdict: WRONG ANSWER

Test 21

Group: 2

Verdict: TIME LIMIT EXCEEDED

Test 22

Group: 2

Verdict: TIME LIMIT EXCEEDED

Test 23

Group: 2

Verdict: TIME LIMIT EXCEEDED

Test 24

Group: 1, 2

Verdict: WRONG ANSWER

Test 25

Group: 2

Verdict: TIME LIMIT EXCEEDED

Test 26

Group: 1, 2

Verdict: WRONG ANSWER

Test 27

Group: 2

Verdict: TIME LIMIT EXCEEDED

Test 28

Group: 1, 2

Verdict: WRONG ANSWER

Test 29

Group: 2

Verdict: TIME LIMIT EXCEEDED

Test 30

Group: 1, 2

Verdict: WRONG ANSWER

Test 31

Group: 2

Verdict: TIME LIMIT EXCEEDED