[프로그래머스] 합승 택시 요금

다익스트라 응용 문제.

어디까지 같이 합승해서 가는 것이 유리한지를 찾아내는 문제인데,

A, B 뿐만 아니라 S까지 고려해야 하는 것을 빨리 캐치해야 했다!

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

class Solution {
    
    static class Node implements Comparable<Node>{
        int from;
        int dist;

        public Node() {}
        public Node(int from, int dist) {
            this.from = from;
            this.dist = dist;
        }

        @Override
        public int compareTo(Node o) {
            if(this.dist == o.dist) return this.from - o.from;
            return this.dist - o.dist;
        }
    }

    static List<Node>[] adj;
    
    public int solution(int n, int s, int a, int b, int[][] fares) {
        int answer = Integer.MAX_VALUE;

        adj = new List[n + 1];

        for(int i = 1; i <= n; i++) {
            adj[i] = new ArrayList<>();
        }

        for(int i = 0; i < fares.length; i++) {
            int[] arr = fares[i];

            adj[arr[0]].add(new Node(arr[1], arr[2]));
            adj[arr[1]].add(new Node(arr[0], arr[2]));
        }

        int[] distA = dijkstra(n, a);
        int[] distB = dijkstra(n, b);
        int[] distS = dijkstra(n, s);

//        System.out.println(Arrays.toString(distA));
//        System.out.println(Arrays.toString(distB));
//        System.out.println(Arrays.toString(distS));

        for(int i = 1; i <= n; i++) {
            answer = Math.min(answer, distA[i] + distB[i] + distS[i]);
        }

        return answer;
    }
    
    public static int[] dijkstra (int n, int start) {
        PriorityQueue<Node> pq = new PriorityQueue<>();
        pq.add(new Node(start, 0));

        int[] dist = new int[n + 1];

        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[start] = 0;

        while(!pq.isEmpty()) {
            Node node = pq.poll();

            if(node.dist > dist[node.from]) continue;

            for(Node next : adj[node.from]) {
                int d = next.dist;
                int to = next.from;
                int dis = dist[node.from] + d;
                if(dist[to] > dis) {
                    dist[to] = dis;
                    pq.add(new Node(to, dis));
                }
            }
        }

        return dist;
    }
}