[백준] 20160: 야쿠르트 아줌마 야쿠르트 주세요 - JAVA

10 Nov 2023 in Algorithm on 그래프 이론

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

풀이

야쿠르트 아줌마의 판매 경로 10개가 주어진다.

아줌마가 해당 위치에 도착하기 전에 가있어야 아쿠르트를 살 수 있다.

먼저 내 시작위치로부터 각 위치까지 얼마나 걸리는지 다익스트라를 통해 구했다.

야쿠르트 아줌마의 시간을 누적해가면서 경로대로 움직였다.

아줌마의 현재위치부터 다익스트라를 통해 다음 위치까지 시간을 구했고, 해당 시간이 Integer.MAX_VALUE이면 그 다음 위치를 보는 식으로 구현했다.

ans를 갱신하여 정점의 번호가 가장 낮은 것이 정답.

---

메모리: 68732KB

시간: 920ms

언어: Java 11

코드

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

public class Main {
    static class Node implements Comparable<Node> {
        int v;
        int cost;

        public Node(int v, int cost) {
            this.v = v;
            this.cost = cost;
        }

        @Override
        public int compareTo(Node o) {
            return Integer.compare(this.cost, o.cost);
        }
    }

    static int V, E;
    static ArrayList<ArrayList<Node>> list;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        V = Integer.parseInt(st.nextToken());
        E = Integer.parseInt(st.nextToken());

        list = new ArrayList<>();
        for (int i = 1; i <= V + 1; i++) {
            list.add(new ArrayList<>());
        }

        for (int i = 0; i < E; i++) {
            st = new StringTokenizer(br.readLine());
            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            int w = Integer.parseInt(st.nextToken());
            list.get(u).add(new Node(v, w));
            list.get(v).add(new Node(u, w));
        }

        Queue<Integer> yogurtMadam = new LinkedList<>();
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < 10; i++) {
            yogurtMadam.add(Integer.parseInt(st.nextToken()));
        }

        int myStart = Integer.parseInt(br.readLine());

        int[] myDist = dijkstra(myStart);

        long time = 0;
        int ans = 10001;

        if (myStart == yogurtMadam.peek()) {
            ans = myStart;
        }

        while (yogurtMadam.size() > 1) {
            int cur = yogurtMadam.poll();

            int[] dist = dijkstra(cur);

            while (!yogurtMadam.isEmpty() && dist[yogurtMadam.peek()] == Integer.MAX_VALUE) {
                yogurtMadam.poll();
            }

            if (!yogurtMadam.isEmpty()) {
                int next = yogurtMadam.peek();
                time += dist[next];
                if (myDist[next] <= time) {
                    ans = Math.min(ans, next);
                }
            }
        }

        System.out.println(ans == 10001 ? -1 : ans);
    }

    private static int[] dijkstra(int start) {
        PriorityQueue<Node> pq = new PriorityQueue<>();
        int[] dist = new int[V + 1];
        Arrays.fill(dist, Integer.MAX_VALUE);

        pq.add(new Node(start, 0));
        dist[start] = 0;

        while (!pq.isEmpty()) {
            Node cur = pq.poll();

            if (cur.cost > dist[cur.v]) {
                continue;
            }

            for (Node next : list.get(cur.v)) {
                if (dist[next.v] > dist[cur.v] + next.cost) {
                    dist[next.v] = dist[cur.v] + next.cost;
                    pq.add(new Node(next.v, dist[next.v]));
                }
            }
        }

        return dist;
    }

}