[프로그래머스] Level3 - 합승 택시 요금, 2021 카카오 문제

import java.util.*;
class Solution {
    static int N;
    static int[] aNodes, bNodes, sNodes;
    static int[][] map;
    static void dijkstra(int start, int[] nodes, int[][] map){
        boolean[] visit = new boolean[N+1];
        Queue<Dist> pq = new PriorityQueue<>();
        pq.add(new Dist(start, 0));
        nodes[start] = 0;
        while(!pq.isEmpty()){
            Dist d = pq.poll();
            if(visit[d.n]) continue;
            visit[d.n] = true;
            for(int i=1; i<map[d.n].length; i++){
                if(!visit[i] && map[d.n][i] > 0 && nodes[i] > nodes[d.n] + map[d.n][i]){
                    nodes[i] = nodes[d.n] + map[d.n][i];
                    pq.add(new Dist(i, nodes[i]));
                }
            }
        }
    }
    static public int solution(int n, int s, int a, int b, int[][] fares) {
        N = n;
        map = new int[N+1][N+1];
        aNodes = new int[N+1];
        bNodes = new int[N+1];
        sNodes = new int[N+1];
        for(int i=0; i<fares.length; i++){
            map[fares[i][0]][fares[i][1]] = fares[i][2];
            map[fares[i][1]][fares[i][0]] = fares[i][2];
        }
        for(int i=1; i<=N; i++){
            aNodes[i] = Integer.MAX_VALUE;
            bNodes[i] = Integer.MAX_VALUE;
            sNodes[i] = Integer.MAX_VALUE;
        }
        dijkstra(a, aNodes, map);
        dijkstra(b, bNodes, map);
        dijkstra(s, sNodes, map);
        
        int answer = Integer.MAX_VALUE;
        for(int i=1; i<=N; i++){
            answer = Math.min(aNodes[i] + bNodes[i] + sNodes[i], answer);
        }
        return answer;
    }

    static class Dist implements Comparable<Dist>{
        int n, v;
        public Dist(int n, int v){
            this.n=n;
            this.v=v;
        }

        @Override
        public int compareTo(Dist o) {
            return this.v - o.v;
        }
    }

}