[KOITP] 워프

출    처 : http://koitp.org/problem/SDS_PRO_10_3/read/

시간 제한	메모리 제한	제출 횟수	정답 횟수 (비율)	정답자 수
1.0 초	512 MB	1895	235 (12%)	165

문제

우주에 N개의 행성이 있다. 어떤 행성쌍에는 워프장치가 존재하는데 ai행성에서 bi행성으로 워프를 타고 ci시간만에 이동할 수 있다. 이때, 워프장치가 설치되어 있는 형태는 ai < bi를 만족한다. 또한, 행성 간의 이동은 오직 워프장치를 통해서만 할 수 있다. 1번 행성에 N번 행성까지 이동하려고 할 때, 최소로 드는 시간을 구하여라.

입력

첫 번째 줄에 행성의 개수 N과 워프장치의 개수 M이 공백으로 분리되어 주어진다. (1 ≤ N ≤ 100,000, 1 ≤ M ≤ 500,000)

두 번째 줄부터 각 워프장치의 정보가 (ai, bi, ci)의 형태로 주어진다. (1 ≤ ai, bi ≤ N, 1 ≤ ci ≤ 100,000)

출력

첫 번째 줄에 1번 행성에서 N번 행성에 도달하는 최소의 시간을 출력한다. 만약 그러한 경로가 없다면 -1을 출력한다.

힌트

입력 예제

3 3
1 2 1
2 3 1
1 3 3

출력 예제

2

< Comment >

 기존에 풀던 것들은 다익스트라를 딱히 최적화 해 주지 않아도 풀 수 있는 문제들이었으나, 이번 문제와 같은 경우에는 최적화를 해 주지 않으면 시간 초과가 발생했다. 기본적으로 다익스트라를 잘못 이해하고 있었던 것 같다. 우선 큐 대신에 우선순위 큐를 써서 가장 짧은 경로부터 릴랙싱을 진행한다. 재귀호출식으로 구현을 했었는데, 그렇게 하게 되면 DFS 방식으로 돌아가기 때문에 다소 적합하지 않은 것 같다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.StringTokenizer;

public class Warp {
	
	public static int N = 0;
	public static int M = 0;
	
	public static long INF = Long.MAX_VALUE;
	
	public static ArrayList<Node> adjust[] = null;
	public static long Relaxing[] = null;
	public static boolean isVisited[] = null;
	
	public static class Node {
		
		int to;
		long coast;
		long relaxing;
		
		public Node(int to, int coast, long relaxing) {
			this.to = to;
			this.coast = coast;
			this.relaxing = relaxing;
		}
		
		public int getTo() {
			return to;
		}
		
		public long getCoast() {
			return coast;
		}
		
		public long getRelaxing() {
			return relaxing;
		}
		
		public void setRelaxing(long relaxing) {
			this.relaxing = relaxing;
		}
	}
	
	public static void main(String[] args) throws Exception {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
	
		isVisited = new boolean[N + 1];
		Relaxing = new long[N + 1];
		for (int i = 0 ; i <= N ; i++) {
			Relaxing[i] = INF;
		}
		Relaxing[1] = 0;
		adjust = new ArrayList[N + 1];
		for (int i = 1 ; i <= N ; i++) {
			adjust[i] = new ArrayList<>();
		}
		
		int a = 0;
		int b = 0;
		int c = 0;
		for (int i = 1 ; i <= M ; i++) {
			st = new StringTokenizer(br.readLine());
			a = Integer.parseInt(st.nextToken());
			b = Integer.parseInt(st.nextToken());
			c = Integer.parseInt(st.nextToken());
			
			adjust[a].add(new Node(b, c, INF));
		}
		
		Dijkstra();
		
		if (Relaxing[N] == INF) {
			bw.write("-1");
		} else {			
			bw.write("" + Relaxing[N]);
		}
		
		bw.flush();
		bw.close();
	}
	
	public static void Dijkstra() {
				
		PriorityQueue<Node> pq = new PriorityQueue<>(N, new Comparator<Node>() {

			@Override
			public int compare(Node arg0, Node arg1) {
				if (arg0.getRelaxing() > arg1.getRelaxing())	return 1;
				if (arg0.getRelaxing() < arg1.getRelaxing())	return -1;
				return 0;
			}

		});
		
		pq.add(new Node(1, 0, 0));
		
		while (!pq.isEmpty()) {
			
			int node = pq.poll().getTo();
			if (isVisited[node])	continue;
			isVisited[node] = true;
			
			for (Node to : adjust[node]) {
				
				int toNode = to.getTo();
				long toCoast = to.getCoast();
				
				long newRel = Relaxing[node] + toCoast;
				if (Relaxing[toNode] > newRel) {
					Relaxing[toNode] = newRel;
					to.setRelaxing(newRel);
					pq.add(to);
				}
			}
		}
	}
}