[JAVA] 백준 12441, 12442 - 약속장소 정하기(Small, Large)

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

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

도시의 개수, 사람 수, 사람 별 출발 도시 정보, 도로 수가 주어지고 사람 별 도로 길이 1당 이동 소요시간과 간선의 정보가 주어졌을 때 어느 도시에서 만나야 소요시간이 가장 적은지 구하는 문제이다.

 

각 사람별 위치한 도시 기준으로 다익스트라를 돌려 모두 도달 가능한 도시에서 각 사람별 이동 소요시간의 최댓값을 구한 뒤 도시별 최솟값을 구해 해결했다.

 

플로이드-워셜을 써도 될 것 같은 문제이다.

 

Large를 풀었더니 Small이 공짜였다.

 

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 t = par(br.readLine());
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < t; i++) {
            int[] info = getArray(br.readLine());
            int nodeCount = info[0];
            int startCount = info[1];
            int roadCount = info[2];
            int[] startNodes = new int[startCount];
            int[] moveCost = new int[nodeCount + 1];
            int[][] dist = new int[startCount][nodeCount+1];
            for (int j = 0; j < startCount; j++) {
                info = getArray(br.readLine());
                startNodes[j] = info[0];
                moveCost[j] = info[1];
                Arrays.fill(dist[j],Integer.MAX_VALUE);
            }
            List<List<Pairs>> list = new ArrayList<>();
            for (int j = 0; j <= nodeCount; j++) {
                list.add(new ArrayList<>());
            }
            for (int j = 0; j < roadCount; j++) {
                info = getArray(br.readLine());
                int cost = info[0];
                for (int k = 2; k < info.length-1 ; k++) {
                    list.get(info[k]).add(new Pairs(info[k+1],cost));
                    list.get(info[k+1]).add(new Pairs(info[k],cost));
                }
            }
            PriorityQueue<Pairs> pq = new PriorityQueue<>();
            for (int j = 0; j < startCount; j++) {
                int targetNode = startNodes[j];
                int moveFee = moveCost[j];
                dist[j][targetNode] = 0;
                Pairs start = new Pairs(targetNode,dist[j][targetNode]);
                pq.offer(start);
                while(!pq.isEmpty()){
                    Pairs poll = pq.poll();
                    int value = poll.to;
                    int weight = poll.weight;
                    if(weight>dist[j][value])continue;
                    List<Pairs> rList = list.get(value);
                    for (int k = 0; k < rList.size(); k++) {
                        Pairs targetRoad = rList.get(k);
                        int to = targetRoad.to;
                        int cost = targetRoad.weight * moveFee;
                        if(dist[j][to]>weight+cost){
                            dist[j][to] = weight+cost;
                            Pairs offer = new Pairs(to, dist[j][to]);
                            pq.offer(offer);
                        }
                    }
                }

            }
            int totalmin = Integer.MAX_VALUE;
            for (int j = 1; j <= nodeCount; j++) {
                int max = Integer.MIN_VALUE;
                boolean flag = false;
                for (int k = 0; k < startCount; k++) {
                    if(dist[k][j]==Integer.MAX_VALUE) {
                        flag = true;
                        break;
                    }
                    max = Math.max(max, dist[k][j]);
                }
                if(flag) continue;
                totalmin = Math.min(totalmin,max);
            }
            System.out.println("Case #"+(i+1)+": "+ (totalmin==Integer.MAX_VALUE?-1:totalmin));

        }
    }

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

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



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

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

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