문제

풀이

• 도로는 양방향이므로 destination에서 다익스트라 진행하면 각 source별 최단거리를 구할 수 있다.

코드

import java.util.*;
class Solution {
    static ArrayList<Road>[] adj;
    static int[] d;
    
    public int[] solution(int n, int[][] roads, int[] sources, int destination) {
        adj=new ArrayList[n+1];
        for(int i=1;i<n+1;i++)adj[i]=new ArrayList<>();
        for(int[] r:roads){
            int a=r[0];
            int b=r[1];
            adj[a].add(new Road(b,1));
            adj[b].add(new Road(a,1));
        }
        d=new int[n+1];
        Arrays.fill(d,Integer.MAX_VALUE);
        dijk(destination);
        int[] answer=new int[sources.length];
        int idx=0;
        for(int s:sources){
            if(d[s]==Integer.MAX_VALUE)answer[idx++]=-1;
            else answer[idx++]=d[s];
        }
        return answer;
    }
    
    static void dijk(int start){
        d[start]=0;
        PriorityQueue<Road> pq=new PriorityQueue<>();
        pq.add(new Road(start,0));
        while(!pq.isEmpty()){
            Road now=pq.poll();
            if(now.dis>d[now.to])continue;
            for(Road r:adj[now.to]){
                if(d[r.to]>r.dis+now.dis){
                    pq.add(new Road(r.to,r.dis+now.dis));
                    d[r.to]=r.dis+now.dis;
                }
            }
        }
    }
    
    static class Road implements Comparable<Road>{
        int dis;
        int to;
        
        public Road(int to,int dis){
            this.to=to;
            this.dis=dis;
        }
        
        public int compareTo(Road o){
            return this.dis-o.dis;
        }
    }    
}

#다익스트라