[백준] 5972: 택배 배송 - JAVA

in Algorithm on 그래프 이론

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

풀이

1부터 N까지 이동해야하는데 길마다 지불해야할 비용이 있다.

즉, 다익스트라 알고리즘을 이용해 최솟값을 구해준다.

ArrayList로 연결된 지점과 비용을 저장하고

dist배열을 만들고 최댓값으로 초기화해준다.

현재칸과 연결된 칸의 비용을 보면서 dist[다음칸]이 (dist[현재칸] + 비용)보다 크다면

더 작은 비용으로 이동할 수 있다는 것이므로 갱신해준다.

메모리: 41024KB

시간: 484ms

언어: 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 N, M;
    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());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

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

        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());

            list.get(a).add(new Node(b, c));
            list.get(b).add(new Node(a, c));
        }

        System.out.println(dijkstra());
    }

    private static int dijkstra() {
        boolean[] visit = new boolean[N + 1];
        int[] dist = new int[N + 1];
        Arrays.fill(dist, Integer.MAX_VALUE);

        PriorityQueue<Node> pq = new PriorityQueue<>();
        pq.offer(new Node(1, 0));
        dist[1] = 0;

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

            if (visit[curr.v]) {
                continue;
            }
            visit[curr.v] = true;

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

        return dist[N];
    }

}