[JAVA] 백준 13424 - 비밀 모임

https://www.acmicpc.net/problem/13424

https://ghcode.tistory.com/297

[JAVA] 백준 12834 - 주간 미팅

12834번 주간 미팅과 동일한 방법의 문제로, 여러개의 출발점에서 가장 가까운 노드 번호를 구하는 문제이다.

N개의 출발점에 대해 다익스트라를 각각 돌리고, 거리의 합이 가장 작은 노드를 구하되, 거리가 같으면 작은 번호를 출력하도록 구현했다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.PriorityQueue;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int a = par(br.readLine());
        for (int j = 0; j < a; j++) {
            int[] info = getArray(br.readLine());
            int nodeCount = info[0];
            int roadCount = info[1];
            List<List<P13424>> list = new ArrayList<>();
            for (int i = 0; i <= nodeCount; i++) {
                list.add(new ArrayList<>());
            }
            for (int i = 0; i < roadCount; i++) {
                int[] v = getArray(br.readLine());
                list.get(v[0]).add(new P13424(v[1], v[2]));
                list.get(v[1]).add(new P13424(v[0], v[2]));
            }
            int startCount = par(br.readLine());
            int[] startArr = getArray(br.readLine());
            int[][] dist = new int[startCount][nodeCount + 1];
            PriorityQueue<P13424> pq = new PriorityQueue<>();
            for (int i = 0; i < startCount; i++) {
                Arrays.fill(dist[i], Integer.MAX_VALUE);
                P13424 start = new P13424(startArr[i], 0);
                dist[i][startArr[i]] = 0;
                pq.offer(start);
                while (!pq.isEmpty()) {
                    P13424 poll = pq.poll();
                    int value = poll.to;
                    int cost = poll.weight;
                    if (cost < dist[i][value]) continue;
                    List<P13424> rList = list.get(value);
                    for (int k = 0; k < rList.size(); k++) {
                        P13424 road = rList.get(k);
                        if (cost + road.weight < dist[i][road.to]) {
                            dist[i][road.to] = cost + road.weight;
                            P13424 offer = new P13424(road.to, cost + road.weight);
                            pq.offer(offer);
                        }
                    }
                }
            }
            int min = Integer.MAX_VALUE;
            int midx =-1;
            for (int i = nodeCount; i >=1 ; i--) {
                int sum = 0;
                for (int k = 0; k < startCount; k++) {
                    sum +=dist[k][i];
                }
                if(sum<=min){
                    min = sum;
                    midx = i;
                }
            }
            System.out.println(midx);
        }

    }

    static int par(String s) {
        return Integer.parseInt(s);
    }

    static int[] getArray(String s) {
        return Arrays.stream(s.split(" ")).mapToInt(Integer::parseInt).toArray();
    }
}

class P13424 implements Comparable<P13424> {
    int to;
    int weight;

    P13424(int t, int weight) {
        this.to = t;
        this.weight = weight;
    }

    @Override
    public int compareTo(P13424 o) {
        return this.weight - o.weight;
    }
}