[백준] 1916번 최소 비용 구하기

[CMSSKKK]

TITLE

최소 비용 구하기

다익스트라 복습하기

LINK

• 문제 출처 사이트 : 백준
• Link

📷 Screenshots

댓글 양식

• 아래 양식을 복사한 뒤 [shift]+[tab] 2회를 하고 작성하여 주세요

    ### 풀이 언어

    - python/java

    ### 코드

    ```python/java

    ```

    ### 핵심 로직 혹은 자료구조

    - 

    ### 시간 복잡도

    - O(  )

[CMSSKKK]

풀이 언어

• java

코드

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

public class Main {

    private static List<List<Node>> graph;
    private static int[] times;

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int m = Integer.parseInt(br.readLine());
        graph = new ArrayList<>();

        for (int i = 0; i < n + 1; i++) {
            graph.add(new ArrayList<>());
        }
        StringTokenizer st;
        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            int s = Integer.parseInt(st.nextToken());
            int d = Integer.parseInt(st.nextToken());
            int w = Integer.parseInt(st.nextToken());

            graph.get(s).add(new Node(d, w));
        }

        times = new int[n+1];
        Arrays.fill(times, Integer.MAX_VALUE);
        st = new StringTokenizer(br.readLine());
        int start = Integer.parseInt(st.nextToken());
        int end = Integer.parseInt(st.nextToken());

        int result = search(start, end, n);
        System.out.println(result);
    }

    private static int search(int start, int end, int n) {
        boolean[] visit = new boolean[n + 1];
        PriorityQueue<Node> pq = new PriorityQueue<>();
        pq.offer(new Node(start, 0));
        times[start] = 0;
        while (!pq.isEmpty()) {
            Node node = pq.poll();
            int curr = node.next;
            if(visit[curr]) {
                continue;
            }
            visit[node.next] = true;
            for(Node no : graph.get(curr)) {

                if (!visit[no.next] && times[no.next] > times[curr] + no.weight) {
                    times[no.next] = times[curr] + no.weight;
                    pq.add(new Node(no.next, times[no.next]));
                }
            }

        }

        return times[end];
    }

    private static class Node implements Comparable<Node>{
        int next;
        int weight;

        public Node(int next, int weight) {
            this.next = next;
            this.weight = weight;
        }

        @Override
        public int compareTo(Node o) {
            return this.weight - o.weight;
        }
    }
}

핵심 로직 혹은 자료구조

• 다익스트라

시간 복잡도

• O( )