[KOITP] 보물섬

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

시간 제한	메모리 제한	제출 횟수	정답 횟수 (비율)	정답자 수
1.0 초	512 MB	2632	473 (18%)	354

문제

강희는 악마의 바다에 어마어마한 보물이 숨겨져 있는 보물섬이 있다는 정보를 입수했다. 하지만 악마의 바다에는 해류가 매우 복잡하게 흐르고 있기 때문에 강희는 좀처럼 보물을 얻고 돌아올 길을 찾기가 힘들어 여러분에게 도움을 요청했다. 강희가 악마의 바다에서 보물을 찾아올 수 있는 최단 시간을 계산하자.

악마의 바다에는 1번부터 N번까지 섬이 N개가 있으며, 서로 다른 섬들을 연결하는 해류가 M개 존재한다. 해류는 한 방향으로만 흐르며 어떤 두 쌍을 잇는 해류가 여러개 존재할 수도 있다. 강희는 현재 1번 섬에 있으며, 보물섬에 들렀다가 다시 1번 섬으로 돌아와 악마의 바다를 탈출하려고 한다.

입력

첫 번째 줄에 줄에는 섬의 개수 N과 섬들을 잇는 해류의 개수 M이 공백으로 분리되어 주어진다. (2 ≤ N ≤ 3,000, 1 ≤ M ≤ 20,000)

두 번째 줄에는 보물섬의 번호 T가 주어진다. (2 ≤ T ≤ N)

세 번째 줄부터 M개의 줄에 걸쳐 각 줄마다 해류의 정보를 나타내는 세 자연수 Xi, Yi, Zi가 주어진다. Xi는 해류의 시작섬 번호, Yi는 해류의 도착섬 번호, Zi는해류를 타고 섬과 섬을 이동하는데 걸리는 시간을 나타낸다. (1 ≤ Xi, Yi ≤ N, 1 ≤ Zi ≤ 1,000)

출력

첫 번째 줄에 강희가 1번 섬에서 출발해 보물을 찾아 다시 1번 섬으로 돌아올 수 있는지 여부를 첫 줄에 출력한다. 돌아올 수 있는 경우 YES, 아닌 경우 NO를 출력한다.

만약, 첫 번째 줄에 YES를 출력한 경우에는 두 번째 줄에 보물을 찾아 악마의 바다를 탈출하는데 드는 최단 시간을 출력한다.

힌트

예제 입력

3 4
3
1 2 4
2 3 3
3 2 2
3 1 1

예제 출력

YES
8

< Comment >

 제대로 된 답이 안 나와서 한참 헤매었는데, 결국 보물섬을 T로 놓고 풀어야 했는데, N으로 놓고 풀어서 답이 어중간하게 맞은 것이었습니다. 문제를 잘 읽는 것도 중요한데, 아직 너무 부주의한 것 같습니다.

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.Collections;
import java.util.StringTokenizer;

public class TreasureIsland {
	
	public static int N = 0;
	public static int M = 0;
	public static int T = 0;
	
	public static ArrayList<Node>[] arr = null;
	public static int Relaxing[] = null;
	
	public static int INF = Integer.MAX_VALUE;
	
	public static class Node {
		
		int to = 0;
		int coast = 0;
		
		public Node(int to, int coast) {
			this.to = to;
			this.coast = coast;
		}
		
		public int getTo() {
			return to;
		}
		
		public int getCoast() {
			return coast;
		}
		
	}

	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());
		
		T = Integer.parseInt(br.readLine());
		
		arr = new ArrayList[N + 1];
		for (int i = 1 ; i <= N ; i++) {
			arr[i] = new ArrayList<Node>();
		}
		
		int from = 0;
		int to = 0;
		int coast = 0;
		for (int i = 1 ; i <= M ; i++) {
			
			st = new StringTokenizer(br.readLine());
			from = Integer.parseInt(st.nextToken());
			to = Integer.parseInt(st.nextToken());
			coast = Integer.parseInt(st.nextToken());
			
			arr[from].add(new Node(to, coast));
		}
		
		Relaxing = new int[N + 1];
		for (int i = 2 ; i <= N ; i++) {
			Relaxing[i] = INF;
		}
		Relaxing[1] = 0;
		
		Daijkstra(1);
		int whenGo = Relaxing[T];
		
		Relaxing = new int[N + 1];
		for (int i = 1 ; i < N ; i++) {
			Relaxing[i] = INF;
		}
		Relaxing[T] = 0;
		
		Daijkstra(T);
		int whenBack = Relaxing[1];
		
		if (whenGo == INF || whenBack == INF) {
			bw.write("NO\n");
		} else {
			bw.write("YES\n" + (whenGo + whenBack) + "\n");
		}
			
		bw.flush();
		bw.close();
	}
	
	public static void Daijkstra(int node) {
		
		if(arr[node] == null)	return;
		
		ArrayDeque<Integer> dq = new ArrayDeque<>();
		for (Node n : arr[node]) {
			
			int newRel = Relaxing[node] + n.getCoast();
			if(Relaxing[n.getTo()] > newRel) {
				Relaxing[n.getTo()] = newRel;
				dq.addLast(n.getTo());
			}
		}
		
		while(!dq.isEmpty()) {			
			Daijkstra(dq.pollFirst());
		}
	}
}