백준 3125번
https://www.acmicpc.net/problem/3125

문제

---

생각하기

---

✔️ 다익스트라 문제로 분류가 되는데, 맨날 하던 갱신은 또 아니라서, 색달랐음

동작

        while (!pque.isEmpty()) {
            Node current = pque.poll();

            if (isVisited[current.num]) continue;
            if (dist[current.num] < current.dist) continue;
            isVisited[current.num] = true;
            dist[current.num] = current.dist;

            int ar = sparkCoors[current.num].arrowCount;
            for (int next : adjList.get(current.num)) {
                if (ar == 0) break; // 남은 화살이 없으면 진행할 수 없음
                if (isVisited[next]) continue;

                double time = dists[current.num][next];
                if (dist[next] <= dist[current.num] + time) continue;

                pque.offer(new Node(next, dist[current.num] + time));
                ar--;
            }
        }

구현해야 할 부분은 그냥 현재 가지고 있는 화살이 있는지 여부, 방문을 했던 곳인지 여부, 화살은 남아 있지만 이미 켜진 스파크이므로 다음 화살을 쏠 곳으로 화살을 쏘기 이 정도만 생각하고 구현하면 되는거 같다.

처음에 최단시간 갱신으로 dist[next] = dist[current] + time으로 해줬는데, 이렇게 하는게 아니었고, 그냥 먼저 들어온 친구 순서대로 진행만하면 된다. 다만 Heap을 사용해서 시간이 빠른 순서대로 정렬은 해야함

혹시 이해가 안되거나 정답이 필요하신 분들은
https://hsin.hr/2008/index.html 로 가셔서 National Competition #1 Solutions를 클릭 후 직접 보는 것도 좋은 방법일 것 같습니다.

결과

코드

---

import java.io.*;
import java.util.*;

public class Main {

    // input
    private static BufferedReader br;

    // variables
    private static final String POINT = "%.6f";
    private static final int INF = Integer.MAX_VALUE;
    private static int N;
    private static double[][] dists;
    private static Coordinate[] sparkCoors;
    private static List<List<Integer>> adjList;

    private static class Coordinate {
        int x;
        int y;
        int arrowCount;

        private Coordinate(int x, int y, int arrow) {
            this.x = x;
            this.y = y;
            this.arrowCount = arrow;
        }
    } // End of Coordinate class

    private static class Node implements Comparable<Node> {
        int num;
        double dist;

        private Node(int num, double dist) {
            this.num = num;
            this.dist = dist;
        }

        @Override
        public int compareTo(Node o) {
            return Double.compare(dist, o.dist);
        }
    } // End of Node class

    public static void main(String[] args) throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        input();

        bw.write(solve());
        bw.close();
    } // End of main()

    private static String solve() throws IOException {
        StringBuilder sb = new StringBuilder();

        for (int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            int ar = Integer.parseInt(st.nextToken());

            sparkCoors[i + 1] = new Coordinate(x, y, ar);
            for (int j = 0; j < N - 1; j++) {
                int next = Integer.parseInt(st.nextToken());
                adjList.get(i + 1).add(next);
            }
        }

        // 각 스파크별 거리 미리 계산
        for (int i = 1; i <= N; i++) {
            Coordinate temp = sparkCoors[i];

            for (int j = 1; j <= N; j++) {
                if (i == j) continue;
                Coordinate temp2 = sparkCoors[j];
                dists[i][j] = distCalc(temp.x, temp.y, temp2.x, temp2.y);
            }
        }

        // 다익스트라
        double[] dist = dijkstra(1);
        for (int i = 1; i <= N; i++) {
            String format = String.format(POINT, dist[i]);
            sb.append(format).append('\n');
        }

        return sb.toString();
    } // End of solve()

    private static double[] dijkstra(int start) {
        PriorityQueue<Node> pque = new PriorityQueue<>();
        boolean[] isVisited = new boolean[N + 1];
        double[] dist = new double[N + 1];
        Arrays.fill(dist, INF);

        dist[start] = 0;
        pque.offer(new Node(start, 0));

        while (!pque.isEmpty()) {
            Node current = pque.poll();

            if (isVisited[current.num]) continue;
            if (dist[current.num] < current.dist) continue;
            isVisited[current.num] = true;
            dist[current.num] = current.dist;

            int ar = sparkCoors[current.num].arrowCount;
            for (int next : adjList.get(current.num)) {
                if (ar == 0) break; // 남은 화살이 없으면 진행할 수 없음
                if (isVisited[next]) continue;

                double time = dists[current.num][next];
                if (dist[next] <= dist[current.num] + time) continue;

                pque.offer(new Node(next, dist[current.num] + time));
                ar--;
            }
        }

        return dist;
    } // End of dijkstra()

    private static double distCalc(int x1, int y1, int x2, int y2) {
        return Math.sqrt(Math.pow(x1 - x2, 2) + Math.pow(y1 - y2, 2));
    } // End of distCalc()

    private static void input() throws IOException {
        N = Integer.parseInt(br.readLine());
        sparkCoors = new Coordinate[N + 1];
        adjList = new ArrayList<>();
        dists = new double[N + 1][N + 1];

        for (int i = 0; i <= N; i++) {
            adjList.add(new ArrayList<>());
        }
    } // End of input()
} // End of Main class