[백준] 1238 파티 [자바]

 

 

---

https://steady-coding.tistory.com/106

[BOJ] 백준 1238번 : 파티 (JAVA)

https://m.blog.naver.com/ndb796/221234424646

23. 다익스트라(Dijkstra) 알고리즘

 

---

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
class Node implements Comparable<Node>{
	int to, time;
	Node(int to, int time) {
		this.time = time;
		this.to = to;
	}
	public int compareTo(Node n) {
		return Integer.compare(this.time, n.time);
	}
}
public class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
		int X = Integer.parseInt(st.nextToken());
		ArrayList<ArrayList<Node>> list = new ArrayList<>();
		ArrayList<ArrayList<Node>> reverse_list = new ArrayList<>();
		for(int i = 0; i <= N; i++) {
			list.add(new ArrayList<>());
			reverse_list.add(new ArrayList<>());
		}
		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 t = Integer.parseInt(st.nextToken());
			list.get(a).add(new Node(b,t));
			reverse_list.get(b).add(new Node(a,t));
		}
		int[] dist = Dijkstra(list,X,N);
		int[] dist1 = Dijkstra(reverse_list, X, N);
		int ans = 0;
		for(int i = 1; i <= N; i++) {
			ans = Math.max(ans, dist[i] + dist1[i]);
		}
		System.out.println(ans);
	}
	static int[] Dijkstra(ArrayList<ArrayList<Node>> list, int X, int N) {
		PriorityQueue<Node> prque = new PriorityQueue<>();
		int[] dis = new int[N+1];
		Arrays.fill(dis, Integer.MAX_VALUE);
		dis[X] = 0;
		prque.add(new Node(X,0));
		while(!prque.isEmpty()) {
			Node n = prque.poll();
			for(Node t : list.get(n.to)) {
				if(t.time+n.time < dis[t.to]) {
					prque.add(new Node(t.to, t.time+n.time));
					dis[t.to] = t.time+n.time;
				}
			}
		}
		return dis;
	}
}