[백준 - 1238] 골드3 - 파티

www.acmicpc.net/problem/1238

1238번: 파티

 

1. 유형

다익스트라, 그래프

 

2. 풀이

 

1) 모든 점에서 다익스트라를 돌려서 X까지의 거리를 구한다.

2) X에서 다익스트라를 돌려서 각 마을까지의 최단거리를 구한다.

3) X까지 간거리와 본인 마을로 돌아온 거리를 더한 후, 최대값을 구한다

 

자료구조: 인접리스트, 우선순위큐

 

인접리스트 구한다

우선순위큐 사용을 위해 클래스 구현

X마을 까지의 최단거리를 구한다

 

3. 코드

package 그래프;

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

public class Beak_1238파티 {
	static int N, M, X;
	static class Pair implements Comparable<Pair>{
		int node, wei;
		public Pair(int node, int wei) {
			this.node = node;
			this.wei = wei;
		}
		@Override
		public int compareTo(Pair o) {
			return this.wei - o.wei;
		}
		
	}
	public static void main(String[] args) throws IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(in.readLine(), " ");
		N = Integer.valueOf(st.nextToken());
		M = Integer.valueOf(st.nextToken());
		X = Integer.valueOf(st.nextToken());
		ArrayList<Pair> list[] = new ArrayList[N+1];
		for(int i=0; i<=N; i++) {
			list[i] = new ArrayList<>();
		}
		for(int i=0;i<M; i++) {
			st = new StringTokenizer(in.readLine(), " ");
			int from,to,w;
			from = Integer.valueOf(st.nextToken());
			to= Integer.valueOf(st.nextToken());
			w = Integer.valueOf(st.nextToken());
			list[from].add(new Pair(to, w));
		}
		int res[] = new int[N+1];
		for(int i=1; i<=N; i++) {
			int minList[] = new int[N+1];
			for(int j=0; j<=N; j++) {
				minList[j] = Integer.MAX_VALUE;
			}
			PriorityQueue<Pair> pq = new PriorityQueue<>();
			pq.add(new Pair(i,0));
			boolean visit[] = new boolean[N+1];
			minList[i] = 0;
			while(!pq.isEmpty()) {
				Pair cur = pq.poll();
				if(visit[cur.node]) {
					continue;
				}
				if(cur.node==X) {
					res[i] = minList[X];
					break;
				}
				visit[cur.node] = true;
				for(Pair next : list[cur.node]) {
					if(!visit[next.node] && minList[next.node] > minList[cur.node] + next.wei) {
						minList[next.node] = minList[cur.node] + next.wei;
						pq.add(new Pair(next.node, minList[next.node]));
					}
				}
			}
		}
		int minList[] = new int[N+1];
		for(int j=0; j<=N; j++) {
			minList[j] = Integer.MAX_VALUE;
		}
		minList[X] = 0;
		PriorityQueue<Pair> pq = new PriorityQueue<>();
		pq.add(new Pair(X,0));
		boolean visit[] = new boolean[N+1];
		while(!pq.isEmpty()) {
			Pair cur = pq.poll();
			if(visit[cur.node]) {
				continue;
			}
			visit[cur.node] = true;
			for(Pair next : list[cur.node]) {
				if(!visit[next.node] && minList[next.node] > minList[cur.node] + next.wei) {
					minList[next.node] = minList[cur.node] + next.wei;
					pq.add(new Pair(next.node, minList[next.node]));
				}
			}
		}
		int max=0;
		for(int j=1; j<=N; j++) {
			res[j]+=minList[j];
			max = max < res[j] ? res[j] : max;
		}
		System.out.println(max);
	}
}