[백준] 1238. 파티 (java, 다익스트라, 최단 경로)

www.acmicpc.net/problem/1238

1238번: 파티

import java.util.ArrayList;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.Scanner;

class City implements Comparable<City>{
	int node,cost;

	public City(int node, int cost) {
		super();
		this.node=node;
		this.cost = cost;
	}

	@Override
	public int compareTo(City o) {
		return this.cost-o.cost;
	}
	
}

public class Main {
	static int n,m,x;
	static int[] t;
	static ArrayList<City>[] list; // 각 도시의 다음 도시정보, 걸리는 시간
	static int[][] dist;//각 지점에서 다른 지점까지의 최단 경로
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		n=sc.nextInt();
		m=sc.nextInt();
		x=sc.nextInt();
		dist=new int[n+1][n+1];//노드 1~n
		for (int i = 0; i <=n; i++) {
			Arrays.fill(dist[i], -1);
		}
		list=new ArrayList[m+1];
		for (int i = 1; i <=n; i++) {
			list[i]=new ArrayList<>();
		}
		for (int i = 0; i < m; i++) {
			int s=sc.nextInt();
			int e=sc.nextInt();
			int cost=sc.nextInt();
			list[s].add(new City(e,cost)); //방향 그래프다 시작점 => 도착점 
		}
		//모든 지점에서 시작할 때 다른 지점으로 가는 최단 경로 구해준다.
		for (int i = 1; i <=n; i++) {
			PriorityQueue<City> pq=new PriorityQueue<>();
			pq.add(new City(i,0));//시작점, 시간
			while(pq.size()!=0) {
				City temp=pq.poll();
				int time=temp.cost;
				int cur=temp.node;
				if(dist[i][cur]==-1) {
                // 거리가 작은 순으로 나와서 처음 방문하는 것이
                // 즉 최단 시간이다.
					dist[i][cur]=time;
					for(City next:list[cur]) {//현재 지점과 연결된 것 중 시간이 적은 순으로 나오게 될 것임
						int total=time+next.cost;
						int node=next.node;
						pq.add(new City(node,total));
					}
				}
			}
		}
		
		
		int answer=-1;
        //오고가는 시간을 모두 더해줘야된다.
		for (int i = 1; i <=n; i++) {
			if(dist[i][x]+dist[x][i]>answer) {
				answer=dist[i][x]+dist[x][i];
			}
		}
		System.out.println(answer);
		
		
	}
}