[백준] 1238 파티

문제

N개의 숫자로 구분된 각각의 마을에 한 명의 학생이 살고 있다.

어느 날 이 N명의 학생이 X (1 ≤ X ≤ N)번 마을에 모여서 파티를 벌이기로 했다. 이 마을 사이에는 총 M개의 단방향 도로들이 있고 i번째 길을 지나는데 Ti(1 ≤ Ti ≤ 100)의 시간을 소비한다.

각각의 학생들은 파티에 참석하기 위해 걸어가서 다시 그들의 마을로 돌아와야 한다. 하지만 이 학생들은 워낙 게을러서 최단 시간에 오고 가기를 원한다.

이 도로들은 단방향이기 때문에 아마 그들이 오고 가는 길이 다를지도 모른다. N명의 학생들 중 오고 가는데 가장 많은 시간을 소비하는 학생은 누구일지 구하여라.

입력

첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어온다. 시작점과 끝점이 같은 도로는 없으며, 시작점과 한 도시 A에서 다른 도시 B로 가는 도로의 개수는 최대 1개이다.

모든 학생들은 집에서 X에 갈수 있고, X에서 집으로 돌아올 수 있는 데이터만 입력으로 주어진다.

출력

첫 번째 줄에 N명의 학생들 중 오고 가는데 가장 오래 걸리는 학생의 소요시간을 출력한다.

예제 입력 1

4 8 2
1 2 4
1 3 2
1 4 7
2 1 1
2 3 5
3 1 2
3 4 4
4 2 3

예제 출력 1

10

풀이

직전 최단 거리 문제가 시작점 하나에 대한 모든 정점의 최단거리를 구하는 거였다면, 이번 문제는 모든 정점의 자신을 제외한 다른 모든 정점까지의 최단거리 정보를 필요로 했다. 따라서 2차원 dist 배열을 통해 모든 정점의 타 정점까지의 최단거리 정보를 저장했다.

이후에는 정점을 돌면서 i 번째 -> X번째 -> i번째 경로의 최단 거리를 구하면 된다.
따라서 dist[i][X] + dist[X][i] 의 최솟값을 구하면 된다.

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

//그래프에 간선정보 저장위한 노드
class Node{
    int n;
    int dist;
    
    Node(int n, int dist){
    	this.n = n;
    	this.dist = dist;
    }
}
// 우선 순위 큐에 정점별 누적 거리 담는 노드
class PQNode implements Comparable<PQNode>{
    int n;
    int sum_dist;
    
	@Override
	public int compareTo(PQNode o) {
		// TODO Auto-generated method stub
		return this.sum_dist - o.sum_dist;
	}
	PQNode(int n, int sum_dist){
		this.n = n;
		this.sum_dist = sum_dist;
	}
}


class Main
{
	static int N; // 마을의 개수(정점의 수)
	static int M; // 단뱡향 도로의 개수(간선의 수)
	static int X; // 파티를 벌일 마을 번호
	static int[][] dist;
	static ArrayList<Node>[] g;
    
	public static void main(String args[]) throws Exception
	{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(st.nextToken()); // 정점 수
		int M = Integer.parseInt(st.nextToken()); // 간선 수
		int X = Integer.parseInt(st.nextToken()); // 파티열리는 마을 번호
		// 최단 거리 저장 배열 생성 및 초기화
		dist = new int[N+1][N+1];
		for(int i = 1; i <= N; i++) {
			Arrays.fill(dist[i], Integer.MAX_VALUE);
		}
		// 그래프 배열 생성 및 초기화
		g = new ArrayList[N+1];
		for(int i = 1; i <= N; i++) {
			g[i] = new ArrayList<>();
		}
		// 단방향 그래프 정보 입력 받기
		for(int i = 0; i < M; i++) {
			st = new StringTokenizer(br.readLine());
			int fn = Integer.parseInt(st.nextToken());
			int sn = Integer.parseInt(st.nextToken());
			int d = Integer.parseInt(st.nextToken());
			g[fn].add(new Node(sn, d));
		}
		// 모든 마을에 대해 다익스트라 돌리기
		for(int i = 1; i <= N; i++) {
			dijkstra(i);
		}	
        // i 번 -> M번 -> i번 마을까지의 총합 최단 거리중 가장 긴 거리를 가진 마을 찾기
		// M 번 마을은 안빼도 최장 거리 찾는거라 상관X
		int max_dist = 0;
		for(int i = 1; i <= N; i++) {
			int cur_dist = dist[i][X] + dist[X][i];
			max_dist = Math.max(max_dist, cur_dist);
		}
		// 정답 출력
		System.out.println(max_dist);
	}
	
	static void dijkstra(int st) {
		PriorityQueue<PQNode> pq = new PriorityQueue<>();
		// 우선 순위 큐 삽입 및 최단 거리 등록(= 갱신)
		pq.offer(new PQNode(st, 0));
		dist[st][st] = 0;
		
		// 인접 노드에 대해 다익스트라 수행
		while(!pq.isEmpty()) {
			PQNode npq = pq.poll();
			// 가장 최근에 갱신된 최단거리인 경우에만 수행
			if(npq.sum_dist > dist[st][npq.n]) continue;
			// 인접 노드에 대해
			for(Node nn: g[npq.n]) {
				int caledDist = npq.sum_dist + nn.dist;
				// 해당 인접 노드의 최단거리보다 짧은 경우에만 수행
				if(dist[st][nn.n] <= caledDist) continue;
				dist[st][nn.n] = caledDist;
				pq.offer(new PQNode(nn.n, caledDist));
			}
		}
		
		
	}
	
	
}