아이디어

• 다익스트라로 최단경로를 구하는 메소드를 만든다.
  • 그래프는 인접 간선을 빠르게 찾기 위해 인접리스트로 나타냈다.
  • Priority queue를 사용하는 다익스트라를 사용하였다.
    • 시간복잡도 $O(M \lg N)$
• (i..X 최단경로 길이 + X..i 최단경로 길이) 중 최댓값을 찾는다.

코드

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

public class Main {
	static BufferedReader rd = new BufferedReader(new InputStreamReader(System.in));
	static StringTokenizer tk = null;

	static int N, M, X, ans;
	static ArrayList<ArrayList<Node>> graph = new ArrayList<>();
	static PriorityQueue<Node> pq = new PriorityQueue<>((n1, n2) -> n1.w - n2.w);
	static int[] dist;
	
	static final int INF = Integer.MAX_VALUE / 2;
	
	public static void main(String[] args) throws Exception {
		tk = new StringTokenizer(rd.readLine());
		N = Integer.parseInt(tk.nextToken());
		M = Integer.parseInt(tk.nextToken());
		X = Integer.parseInt(tk.nextToken());
		
		for (int i=0; i<=N; i++) {
			graph.add(new ArrayList<>());
		}
		
		for (int i=0; i<M; i++) {
			tk = new StringTokenizer(rd.readLine());
			int a = Integer.parseInt(tk.nextToken());
			int b = Integer.parseInt(tk.nextToken());
			int t = Integer.parseInt(tk.nextToken());
			graph.get(a).add(new Node(b, t));
		}

		dist = new int[N+1];
		for (int i=1; i<=N; i++) {
			ans = Math.max(ans, dijkstra(i, X) + dijkstra(X, i));
		}
		
		System.out.println(ans);
	}
	
	static class Node {
		int v, w;
		Node(int v, int w) {
			this.v = v;
			this.w = w;
		}
	}
	
	static int dijkstra(int s, int e) {
		Arrays.fill(dist, INF);
		dist[s] = 0;
		
		pq.clear();
		pq.offer(new Node(s, 0));
		
		while (!pq.isEmpty()) {
			Node cur = pq.poll();
			
			if (cur.v == e) return cur.w;
			
			for (Node nei: graph.get(cur.v)) {
				if (cur.w + nei.w < dist[nei.v]) {
					dist[nei.v] = cur.w + nei.w;
					pq.offer(new Node(nei.v, dist[nei.v]));
				}
			}
		}
		return -1;
	}
}

메모리 및 시간

• 메모리: 65832 KB
• 시간: 516 ms

리뷰

• 다익아 또 너냐~
• 풀이가 너무 뻔했다.