[BOJ] 1916 최소비용 구하기

다익스트라 예제

문제

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

문제 풀이

package Baekjoon.Graph;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

/**
 * Created by kyeahen.
 * Title : 1916 최소비용 구하기
 * Category : 그래프, 다익스트라
 * Date: 2021/06/16
 */
public class BJ_1916 {

    static class Edge implements Comparable<Edge> {
        int end;
        int cost;

        Edge(int end, int cost) {
            this.end = end;
            this.cost = cost;
        }

        @Override
        public int compareTo(Edge o) {
            return cost - o.cost;
        }
    }

    static int N, M;
    static ArrayList<Edge>[] citys;
    static int[] dist;

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

        N = Integer.parseInt(br.readLine());
        M = Integer.parseInt(br.readLine());

        citys = new ArrayList[N + 1];
        dist = new int[N + 1];

        for (int i = 1; i <= N; i++) {
            citys[i] = new ArrayList<>();
        }

        Arrays.fill(dist, Integer.MAX_VALUE);

        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int s = Integer.parseInt(st.nextToken());
            int e = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());
            citys[s].add(new Edge(e, c));
        }

        st = new StringTokenizer(br.readLine());
        int start = Integer.parseInt(st.nextToken());
        int end = Integer.parseInt(st.nextToken());

        dijkstra(start, end);

    }

    public static void dijkstra(int start, int end) {
        PriorityQueue<Edge> pq = new PriorityQueue<>();
        boolean[] visited = new boolean[N + 1];

        pq.offer(new Edge(start, 0));
        dist[start] = 0;

        while (!pq.isEmpty()) {
            Edge edge = pq.poll();
            int current = edge.end;

            if (visited[current]) { continue; }

            visited[current] = true;

            for (Edge e : citys[edge.end]) {
                if (dist[e.end] > dist[current] + e.cost) {
                    dist[e.end] = dist[current] + e.cost;
                    pq.offer(new Edge(e.end, dist[e.end]));
                }
            }
        }

        System.out.println(dist[end]);
    }
}

TMI

21/06/16: 알고리즘 스터디 문제 풀이🤓