[골드 3] ACM Craft

https://www.acmicpc.net/problem/1005

1005번: ACM Craft

1. 그래프 그려

2. 방향 반대로 해

3. pQ 시간 오래 걸리는 것부터 조사

4. 해당 정점 도착 했을 때 걸린 시간 memorization 해

5. W부터 넣고 해당 정점 도착 했을 때 걸린 시간이 더 적은 액면 아예 안 넣어

6. 모든 정점을 한 번씩 방문했으면 끝내

7. 걸린 시간 최댓값 출력해

8. 왜 시간 초과임?

import java.io.*;
import java.util.*;

class Data {
	int vertex_number;
	int take_time;

	Data(int vertex_number, int take_time) {
		this.vertex_number = vertex_number;
		this.take_time = take_time;
	}
}

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		StringTokenizer st;

		int T;
		T = Integer.parseInt(br.readLine());

		for (int test_case = 1; test_case <= T; test_case++) {
			int N, K;
			int[] times;
			int[][] order;
			int W;

			st = new StringTokenizer(br.readLine());
			N = Integer.parseInt(st.nextToken());
			K = Integer.parseInt(st.nextToken());

			times = new int[N];
			st = new StringTokenizer(br.readLine());
			for (int i = 0; i < N; i++)
				times[i] = Integer.parseInt(st.nextToken());

			order = new int[K][2];
			for (int i = 0; i < K; i++) {
				st = new StringTokenizer(br.readLine());
				order[i][0] = Integer.parseInt(st.nextToken()) - 1;
				order[i][1] = Integer.parseInt(st.nextToken()) - 1;
			}

			W = Integer.parseInt(br.readLine()) - 1;

			///////////////////////////////////////////////////////

			ArrayList<ArrayList<Integer>> graph = new ArrayList<>();
			for (int i = 0; i < N; i++)
				graph.add(new ArrayList<Integer>());

			for (int i = 0; i < K; i++) {
				graph.get(order[i][1]).add(order[i][0]);
			}

			int[] take_times = new int[N];
			for (int i = 0; i < take_times.length; i++)
				take_times[i] = -1;

			PriorityQueue<Data> queue = new PriorityQueue<Data>(new Comparator<Data>() {
				@Override
				public int compare(Data o1, Data o2) {
					if (o1.take_time > o2.take_time)
						return -1;
					else if (o1.take_time == o2.take_time)
						return 0;
					else
						return 1;
				}

			});

			take_times[W] = times[W];
			queue.add(new Data(W, times[W]));

			int count = 0;

			while (!queue.isEmpty()) {
				Data tmp = queue.remove();
				
				if(count >= N)
					break;

				for (int i = 0; i < graph.get(tmp.vertex_number).size(); i++) {
					if (take_times[graph.get(tmp.vertex_number).get(i)] < tmp.take_time
							+ times[graph.get(tmp.vertex_number).get(i)]) {
						if(take_times[graph.get(tmp.vertex_number).get(i)] == -1)
							count++;
						take_times[graph.get(tmp.vertex_number).get(i)] = tmp.take_time
								+ times[graph.get(tmp.vertex_number).get(i)];
						queue.add(new Data(graph.get(tmp.vertex_number).get(i),
								take_times[graph.get(tmp.vertex_number).get(i)]));
						
					}
				}
			}

			long answer = Long.MIN_VALUE;
			for (int i = 0; i < take_times.length; i++)
				answer = Math.max(answer, take_times[i]);
			sb.append(answer).append("\n");

		}
		System.out.println(sb);
	}

}