[백준] 1238 - 파티

[문제링크]

1238번: 파티

 

0. 정점의 범위에 비해 간선의 갯수가 적으므로, 우선순위 큐를 이용해 다익스트라를 실행한다

 

1. i지점에서 다익스트라 실행 : i -> x의 최솟값을 구한다

  - x지점에서 다익스트라 실행 : x -> i의 최솟값을 구한다

 

2. 모든 i에 대해 1번의 결과를 실행 후, 그 최댓값을 출력한다

 

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

public class Main {
	public static void main(String[] args)throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		int n = pint(st.nextToken());
		int m = pint(st.nextToken());
		int x = pint(st.nextToken());
		
		ArrayList<ArrayList<int[]>>graph=new ArrayList<>();
		for (int i = 0; i <= n; i++) {
			graph.add(new ArrayList<>());
		}
		for (int i = 0; i < m; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			graph.get(pint(st.nextToken())).add(new int[] {pint(st.nextToken()),pint(st.nextToken())});
		}
		
		PriorityQueue<int[]>pQ = new PriorityQueue<>(
				new Comparator<int[]>() {
					@Override
					public int compare(int[] o1, int[] o2) {
						return o1[1]-o2[1];
					}
				}
		);
		
		int max=0;
		
		//1. X지점에서 다익스트라(돌아오는 길)
		int[]costX = new int[n+1];//X로부터 다른 지점까지 cost
		Arrays.fill(costX, Integer.MAX_VALUE);
		costX[x]=0;
		for (int i = 1; i <= n; i++) {
			pQ.add(new int[] {i, Integer.MAX_VALUE});
		}
		pQ.add(new int[] {x,0});
		
		while(!pQ.isEmpty()) {
			int[]cur = pQ.poll();
			if(costX[cur[0]] < cur[1])continue;
			
			for (int i = 0; i < graph.get(cur[0]).size(); i++) {
				int[]next = graph.get(cur[0]).get(i);
				//더 짧으면 갱신
				if(costX[cur[0]] + next[1]< costX[next[0]]) {
					costX[next[0]]=costX[cur[0]] + next[1];
					pQ.add(new int[] {next[0], costX[next[0]]});
				}
			}
		}

		//2. 그 외 지점에서 다익스트라(가는 길)
		for (int i = 1; i <= n; i++) {
			if(i==x)continue;
			
			int[]costI = new int[n+1];//X로부터 다른 지점까지 cost
			Arrays.fill(costI, Integer.MAX_VALUE);
			costI[i]=0;
			for (int j = 1; j <= n; j++) {
				pQ.add(new int[] {j, Integer.MAX_VALUE});
			}
			pQ.add(new int[] {i,0});
			
			while(!pQ.isEmpty()) {
				int[]cur = pQ.poll();
				if(costI[cur[0]] < cur[1])continue;
				
				for (int j = 0; j < graph.get(cur[0]).size(); j++) {
					int[]next = graph.get(cur[0]).get(j);
					//더 짧으면 갱신
					if(costI[cur[0]] + next[1]< costI[next[0]]) {
						costI[next[0]]=costI[cur[0]] + next[1];
						pQ.add(new int[] {next[0], costI[next[0]]});
					}
				}
			}
			
			max = Math.max(max, costI[x]+costX[i]);
			
		}
		System.out.println(max);
	}
	static int pint(String s) {
		return Integer.parseInt(s);
	}
}

결과 화면