[BOJ5972] 택배 배송(최단경로, 다익스트라)

 

 

---

문제 링크

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

5972번: 택배 배송

 

문제 풀이

- 다익스트라 알고리즘 문제 

- 1 -> N 노드 까지 최단 거리 구하면 된다

- C_i마리 소 = 간선의 가중치

- 시간 복잡도 : O(ElogV)

- 노드와 간선이 최대 50,000개 있으므로 O(50,000log50,000)  = O(50,000 * 약 15.6) , 고로 1초만에 가능

 

제출 코드

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

public class Main {
    
    static List<Info>[] adj;

    static int n, m;

    static class Info implements Comparable<Info> {
        int idx;
        int cost;

        public Info(int idx, int cost) {
            this.idx = idx;
            this.cost = cost;
        }

        @Override
        public int compareTo(Info info) {
            return cost - info.cost; // 오름차순
        }
    }

    static void input() 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());

        adj = new ArrayList[n + 1];
        for(int i = 1; i <= n; i++) adj[i] = new ArrayList<>();

        for(int i = 1; i <= m; i++) {
            st = new StringTokenizer(br.readLine());
            int from = Integer.parseInt(st.nextToken());
            int to = Integer.parseInt(st.nextToken());
            int cost = Integer.parseInt(st.nextToken());

            adj[from].add(new Info(to, cost));
            adj[to].add(new Info(from, cost));
        }
    }

    // 1 -> N 까지 최소 비용 구한다
    static void dijkstra() {
        Queue<Info> que = new PriorityQueue<>();
        que.add(new Info(1, 0));

        int[] dist = new int[n + 1];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[1] = 0;

        int result = Integer.MAX_VALUE;
        while(!que.isEmpty()) {
            Info cur = que.poll();

            if(cur.idx == n) {
                result = Math.min(result, cur.cost);
                continue;
            }

            if(dist[cur.idx] < cur.cost) continue;

            for(Info next : adj[cur.idx]) {
                if(dist[next.idx] > dist[cur.idx] + next.cost) {
                    dist[next.idx] = dist[cur.idx] + next.cost;
                    que.add(new Info(next.idx, dist[next.idx]));
                }
            }
        }

        System.out.println(result);
    }

    static void pro() {
        dijkstra();
    }

    public static void main(String[] args) throws Exception {
        input();
        pro();
    }
    
}