백준 5972 - 택배 배송

문제

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

리뷰

다익스트라를 이용해 쉽게 풀이할 수 있는 문제였다.

단순히 간선 정보를 통해 양방향 그래프를 설정해주고 다익스트라 로직을 통해
dist[N]을 도출하여 답을 구하였다.

로직의 시간 복잡도는 다익스트라의 $O(MlogN)$로 수렴하고, 이는 $N=M=50,000$인
최악의 경우에도 무난히 제한 조건 1초를 통과한다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

import static java.lang.Integer.MAX_VALUE;
import static java.lang.Integer.parseInt;

public class Main {
    static int N;
    static int[] dist;
    static List<List<Node>> graph=new ArrayList<>();

    public static void main(String[] args) throws IOException {
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st=new StringTokenizer(br.readLine());
        N= parseInt(st.nextToken());
        int M=parseInt(st.nextToken());

        dist=new int[N+1];
        for(int i=0; i<=N; i++)
            graph.add(new ArrayList<>());

        int u, v, w;
        while(M-->0){
            st=new StringTokenizer(br.readLine());
            u=parseInt(st.nextToken());
            v=parseInt(st.nextToken());
            w=parseInt(st.nextToken());

            graph.get(u).add(new Node(v, w));
            graph.get(v).add(new Node(u, w));
        }

        dijkstra(1);
        System.out.println(dist[N]);
        br.close();
    }

    static void dijkstra(int start){
        PriorityQueue<Node> pq=new PriorityQueue<>(Comparator.comparingInt(n->n.w));
        Arrays.fill(dist, MAX_VALUE);
        dist[start]=0;
        pq.offer(new Node(start, dist[start]));

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

            if(dist[cur.v]<cur.w) continue;

            for(Node next:graph.get(cur.v)){
                if(dist[next.v]>cur.w+next.w){
                    dist[next.v]=cur.w+next.w;
                    pq.offer(new Node(next.v, dist[next.v]));
                }
            }
        }

    }
    static class Node{
        int v, w;

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

결과