백준 - 1238번 파티 - java

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

접근법

최단거리 문제이므로 다익스트라 알고리즘을 적용하면 좋다
기본적인 다익스트라 알고리즘을 적용해서
각각 시작지점별로 단방향을 적용해서 최소거리를 구한다
dist테이블이 완성되면, dist[i][x] + dist[x][i] 의 합으로 i -> x / x -> i 의 값을 계산한다
그 합 중 최대값을 출력하면 정답

소스

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

public class Main {
	static ArrayList<Edge>[] graph;
	static int[][] dist;
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int m = sc.nextInt();
		int x = sc.nextInt();
		
		dist = new int[n+1][n+1];
		
		graph = new ArrayList[n+1];
		for(int i = 1; i <= n; i++) {
			graph[i] = new ArrayList<Edge>();
		}
		
		for(int i = 0; i < m; i++) {
			int s = sc.nextInt();
			int e = sc.nextInt();
			int w = sc.nextInt();
			graph[s].add(new Edge(e, w)); //단방향이니 반대는 안함
		}
		
		for(int i = 1; i <= n; i++) {
			dijkstra(i);
		}
		
		int answer = 0;
		
		for(int i = 1; i < n+1; i++) {
			answer = dist[i][x] + dist[x][i] > answer ? dist[i][x] + dist[x][i] : answer;
		}
		System.out.println(answer);
	}
	
	public static void dijkstra(int n) {
		boolean[] visit = new boolean[dist.length];
		for(int i = 1; i < dist.length; i++) {
			dist[n][i] = Integer.MAX_VALUE;
		}
		PriorityQueue<Edge> q = new PriorityQueue<Edge>();
		//시작 설정
		dist[n][n] = 0;
		q.offer(new Edge(n, 0));
		
		while(!q.isEmpty()) {
			Edge cur = q.poll();
			
			//방문 처리
			if(visit[cur.index]) continue;
			else visit[cur.index] = true;
			
			//꺼낸 간선에 연결된 간선들을 탐색
			for(int i = 0; i < graph[cur.index].size(); i++) {
				Edge linkEdge = graph[cur.index].get(i);
				if(dist[n][linkEdge.index] > cur.weight + linkEdge.weight) {
					dist[n][linkEdge.index] = cur.weight + linkEdge.weight;
					q.add(new Edge(linkEdge.index, cur.weight + linkEdge.weight));
				}
			}
		}
	}
}
class Edge implements Comparable<Edge>{
	int index;
	int weight;
	
	Edge(int index, int weight) {
		this.index = index;
		this.weight = weight;
	}
	
	@Override
	public int compareTo(Edge o) {
		// TODO Auto-generated method stub
		return this.weight - o.weight;
	}
}