문제

풀이

• 모든 출발지에서 산봉우리까지의 다익스트라 진행하여 가장 최소 intensity를 찾아준다.
• 인접리스트 구성할 때 출입구, 산봉우리, 일반로 구분해줬다.

  ---

코드

import java.util.*;
class Solution {

        static ArrayList<Road>[] adj;
        static int[] answer;
        static Set<Integer> summitSet;
        static Set<Integer> gateSet;
        static int N;
        static int[] d;

        public int[] solution(int n, int[][] paths, int[] gates, int[] summits) {
            answer = new int[]{50001, 10000001};
            N = n;
            adj = new ArrayList[n + 1];
            for (int i = 0; i < n + 1; i++) adj[i] = new ArrayList<>();
            summitSet = new HashSet<>();
            for (int a : summits) summitSet.add(a);
            gateSet = new HashSet<>();
            for (int a : gates) gateSet.add(a);
            for (int[] path : paths) {
                int a = path[0];
                int b = path[1];
                int c = path[2];
                if(gateSet.contains(a)){
                    adj[a].add(new Road(b, c));
                }
                else if(gateSet.contains(b)){
                    adj[b].add(new Road(a, c));
                }
                else if(summitSet.contains(a)){
                    adj[b].add(new Road(a, c));
                }
                else if(summitSet.contains(b)){
                    adj[a].add(new Road(b, c));
                }
                else {
                    adj[a].add(new Road(b, c));
                    adj[b].add(new Road(a, c));
                }
            }
            d = new int[N + 1];
            Arrays.fill(d, 10000001);


            for(int start:gates){
                dijk(start);
            }

            return answer;
        }

        static void dijk(int start) {
            PriorityQueue<Road> pq = new PriorityQueue<>();
            d[start] = 0;
            int[] v = new int[N + 1];
            pq.add(new Road(start, -1));

            while (!pq.isEmpty()) {
                Road now = pq.poll();
                if (v[now.num] == 1) continue;
                v[now.num] = 1;
                if (d[now.num] < now.intensity) continue;
                for (Road road : adj[now.num]) {
                    int next = road.num;
                    int nextIntensity = Math.max(now.intensity, road.intensity);
                    if (gateSet.contains(next)) continue;
                    if (summitSet.contains(next)) {
                        if (d[next] > nextIntensity) {
                            d[next] = nextIntensity;
                            if(d[next]<answer[1]){
                                answer[1]=d[next];
                                answer[0]=next;
                            }
                            else if(d[next]==answer[1]){
                                answer[0]=Math.min(next,answer[0]);
                            }
                            continue;
                        }
                    }
                    if (v[next] == 0) {

                        if (d[next] >= nextIntensity) {
                            d[next] = nextIntensity;
                            pq.add(new Road(next, nextIntensity));
                        }
                    }
                }
            }
        }

        static class Road implements Comparable<Road> {
            int num;
            int intensity;

            public Road(int num, int intensity) {
                this.num = num;
                this.intensity = intensity;
            }

            @Override
            public int compareTo(Road o) {
                return this.intensity - o.intensity;
            }
        }
    }

#다익스트라