[백준] 1238 파티 - 다익스트라(Dijkstra) JAVA

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

1238번: 파티

코드설명

다익스트라 문제입니다.

 

문제로직입니다.

1. X에서 다른 마을까지 가는 dXToOther[] 를 저장해놓습니다.
2. 다른마을에서 X까지 가는 d[]를 구하며, dXToOther[i] 와 d[X] 의 값의 최대값을 갱신합니다.
3. 최대값을 출력합니다.

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
 
public class Main {
	public static int N, M, X;
	public static int[] arr;
	public static int answer = 0;
	public static int[] d;
	public static int[] dXToOther;
	public static ArrayList<ArrayList<Node>> graph = new ArrayList<ArrayList<Node>>();
    public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer st = new StringTokenizer(br.readLine()); 	
    	
    	N = Integer.parseInt(st.nextToken());
    	M = Integer.parseInt(st.nextToken());
    	X = Integer.parseInt(st.nextToken());
    	
    	d = new int[N+1];
    	dXToOther = new int[N+1];
    	for(int i=0;i<=N;i++) {
    		graph.add(new ArrayList<Node>());
    	}
    	
    	for(int i=0;i<M;i++) {
    		st = new StringTokenizer(br.readLine());
    		int a = Integer.parseInt(st.nextToken());
    		int b = Integer.parseInt(st.nextToken());
    		int c = Integer.parseInt(st.nextToken());
    		graph.get(a).add(new Node(b, c));
    	}
    
    	dijkstra(X);
    	
    	dXToOther = d.clone();
    	
 
    	int maxCnt = 0;
    	int maxIdx = 0;
    	for(int i=1; i<=N;i++) {
    		dijkstra(i);
//    		System.out.println("d:"+d[X] +"dXToOther:"+dXToOther[i]);
    		answer = Math.max(answer , d[X] + dXToOther[i]);
    	}
    	System.out.println(answer);
    	
    }
    
    public static void dijkstra(int start) {
    	Arrays.fill(d,  Integer.MAX_VALUE);
    	
    	PriorityQueue<Node> pq = new PriorityQueue<>();
    	pq.offer(new Node(start, 0));
    	d[start] = 0;
    	
    	while(!pq.isEmpty()) {
    		Node temp = pq.poll();
    		int nodeB = temp.nodeB;
    		int distance = temp.distance;
    		
    		if(d[nodeB] < distance) continue;
    		
    		for(int i=0;i<graph.get(nodeB).size();i++) {
    			int cost = distance + graph.get(nodeB).get(i).distance;
    			if( d[graph.get(nodeB).get(i).nodeB] > cost) {
    				pq.offer(new Node(graph.get(nodeB).get(i).nodeB, cost));
    				d[graph.get(nodeB).get(i).nodeB] = cost;
    			}
    		}
    	}
    	
    }
    
}
 
class Node implements Comparable<Node>{
	int nodeB;
	int distance;
	public Node(int nodeB, int distance) {
		this.nodeB = nodeB;
		this.distance = distance;
	}
	@Override
	public int compareTo(Node other) {
		if(this.distance > other.distance) {
			return 1;
		}else if(this.distance == other.distance) {
			return 0;
		}else {
			return -1;
		}
	}
}