[BaekJoon] 1238 파티 (Java)

1.  문제 링크

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

2.  문제

요약

• N개의 숫자로 구분된 각각의 마을에 한 명의 학생이 살고 있습니다.
• N명의 학생이 X(1 ≤ X ≤ N)번 마을에 모여 파티를 벌이기로 했는데, 마을 사이에는 총 M개의 단방향 도로들이 있고 i번째 길을 지나는데 $T_i$의 시간을 소비합니다.
• 각각의 학생들은 파티에 참석하기 위해 걸어가서 다시 그들의 마을로 돌아와야 하는데, 최단 시간에 오고 가기를 원합니다.
• 도로들은 단방향이기 때문에 오고 가는 길이 다를 수도 있습니다.
• N명의 학생들 중 오고 가는데 가장 많은 시간을 소비하는 학생이 누구인지 구하는 문제입니다.
• 입력: 첫 번째 줄에 1보다 크거나 같고 1,000보다 작거나 같은 N과 1보다 크거나 같고 10,000보다 작거나 같은 M이 주어지고 두 번째 줄부터 M개의 줄에 i번째 도로의 시작점, 끝점, 도로를 지나는데 필요한 소요시간 $T_i$가 주어집니다.
  • 시작점과 끝점이 같은 도로는 없고, 시작점과 한 도시 A에서 다른 도시 B로 가는 도로의 개수는 최대 1개입니다.
  • 모든 학생들은 집에서 X에 갈 수 있고, X에서 집으로 돌아올 수 있는 데이터만 입력됩니다.
• 출력: 첫 번째 줄에 N명의 학생들 중 오고 가는데 가장 오래 걸리는 학생의 소요시간을 출력합니다.

3.  소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {
	static int N, M, X;
	static HashMap<Integer, ArrayList<Edge>> map;
	static void input() {
		Reader scanner = new Reader();
		N = scanner.nextInt();
		M = scanner.nextInt();
		X = scanner.nextInt();
		map = new HashMap<Integer, ArrayList<Edge>>();
		for(int vertex = 1; vertex <= N; vertex++) map.put(vertex, new ArrayList<Edge>());
		for(int index = 0; index < M; index++) {
			int start = scanner.nextInt();
			int end = scanner.nextInt();
			int weight = scanner.nextInt();
			map.get(start).add(new Edge(end, weight));
		}
	}
	
	static void solution() {
		int[][] distances = new int[N + 1][N + 1];
		for(int vertex = 1; vertex <= N; vertex++) {
			dijkstra(vertex, distances[vertex]);
		}
		int max = Integer.MIN_VALUE;
		for(int vertex = 1; vertex <= N; vertex++) {
			int distance = distances[vertex][X] + distances[X][vertex];
			max = Math.max(max, distance);
		}
		System.out.println(max);
	}
	
	static void dijkstra(int start, int[] distance) {
		PriorityQueue<Edge> queue = new PriorityQueue<Edge>();
		queue.offer(new Edge(start, 0));
		Arrays.fill(distance, Integer.MAX_VALUE);
		distance[start] = 0;
		while(!queue.isEmpty()) {
			Edge curEdge = queue.poll();
			if(distance[curEdge.vertex] < curEdge.weight) continue;
			for(Edge e : map.get(curEdge.vertex)) {
				if(distance[e.vertex] > e.weight + distance[curEdge.vertex]) {
					distance[e.vertex] = e.weight + distance[curEdge.vertex];
					queue.offer(new Edge(e.vertex, distance[e.vertex]));
				}
			}
		}
	}
	
	public static void main(String[] args) {
		input();
		solution();
	}
	
	static class Reader {
		BufferedReader br;
		StringTokenizer st;
		public Reader() {
			br = new BufferedReader(new InputStreamReader(System.in));
		}
		String next() {
			while(st == null || !st.hasMoreElements()) {
				try {
					st = new StringTokenizer(br.readLine());
				} catch(IOException e) {
					e.printStackTrace();
				}
			}
			return st.nextToken();
		}
		int nextInt() {
			return Integer.parseInt(next());
		}
	}
	
	static class Edge implements Comparable<Edge> {
		int vertex, weight;
		public Edge(int vertex, int weight) {
			this.vertex = vertex;
			this.weight = weight;
		}
		public int compareTo(Edge e) {
			if(this.weight != e.weight) {
				return this.weight - e.weight;
			} else {
				return this.vertex - e.vertex;
			}
		}
	}
}