[백준] 파티

참고 : www.acmicpc.net/problem/1238

1238번: 파티

 

- 다익스트라 문제

- 풀이를 보고 품

- 어떻게 해서 최단 거리를 구할 지 아이디어가 핵심

- d[N] : x에서 시작점까지의 최단 거리

- rd[N] : 시작점에서 x까지의 최단 거리

 

import java.io.*;
import java.util.*;

class Edge {
    int vertex;
    int weight;
    public Edge(int vertex, int weight) {
        this.vertex = vertex;
        this.weight = weight;
    }
}

public class Solution {
    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int M = sc.nextInt();
        int X = sc.nextInt();
        List<Edge>[] adj = new ArrayList[N];
        List<Edge>[] reverseAdj = new ArrayList[N];
        for(int i =0; i< N; i++) {
            adj[i] = new ArrayList<>();
            reverseAdj[i] = new ArrayList<>();
        }
        for (int i = 0; i < M; i++) {
            int start = sc.nextInt()-1;
            int end = sc.nextInt()-1;
            int weight = sc.nextInt();
            adj[start].add(new Edge(end, weight));
            reverseAdj[end].add(new Edge(start, weight));
        }

        int[] d = dijkstra(N, adj, X-1);
        int[] rd = dijkstra(N, reverseAdj, X-1);


        int max = 0;
        for (int j = 0; j < N; j++) {
            max = Math.max(max, d[j] + rd[j]);
        }

        System.out.println(max);


    }

    private static int[] dijkstra(int N, List<Edge>[] adj, int X) {

        PriorityQueue<Edge> pq = new PriorityQueue<>((a, b) -> a.weight - b.weight);
        pq.offer(new Edge(X, 0));
        int[] d = new int[N];
        Arrays.fill(d, 100001);
        d[X] = 0;
        boolean[] visited = new boolean[N];
        while(!pq.isEmpty()) {
            Edge edge = pq.poll();
            if(visited[edge.vertex]) continue;
            visited[edge.vertex] = true;
            for(Edge bridge : adj[edge.vertex]) {
                if(d[bridge.vertex] > d[edge.vertex] + bridge.weight) {
                    d[bridge.vertex] = d[edge.vertex] + bridge.weight;
                    pq.add(new Edge(bridge.vertex, d[bridge.vertex]));
                }
            }
        }
        return d;
    }
}