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

다익스트라 문제입니다.

시작위치에서 도착위치까지 최소비용을 구해야합니다.
우선순위 큐를 활용해서 다익스트라 알고리즘을 구현해주었습니다.

pq(우선순위큐)에서 값을 뽑아냅니다.
pq는 인덱스와 가중치 정보를 가지고 있습니다.
가중치가 낮은 순으로 차례대로 정점들을 뽑아냅니다.

해당 정점들에서 이동가능한 곳들의 가중치를 구합니다.
해당 정점의 가중치 > 이전 위치의 가중치 + 해당 정점까지의 비용
위의 비용을 비교해서 true라면 값을 갱신해주고 pq에 넣어줍니다.

위의 과정을 반복해서 간선들을 갱신해주고 도착지의 cost를 출력해줍니다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {
  static int n;
  static int bus;
  static ArrayList<ArrayList<Node>> al;
  static PriorityQueue<Node> pq;
  static int start;
  static int end;
  static int[] cost;

  public static void main(String[] args) throws Exception {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    StringTokenizer st = null;

    n = Integer.parseInt(br.readLine());
    bus = Integer.parseInt(br.readLine());
    pq = new PriorityQueue<>((a, b) -> {
      return a.weight - b.weight;
    });
    al = new ArrayList<>();
    cost = new int[n];

    for (int i = 0; i < n; ++i) {
      ArrayList<Node> temp = new ArrayList<>();
      al.add(temp);
      cost[i] = 987654321;
    }

    for (int i = 0; i < bus; ++i) {
      st = new StringTokenizer(br.readLine());
      int a = Integer.parseInt(st.nextToken()) - 1;
      int b = Integer.parseInt(st.nextToken()) - 1;
      int c = Integer.parseInt(st.nextToken());
      al.get(a).add(new Node(b, c));
    }
    st = new StringTokenizer(br.readLine());
    start = Integer.parseInt(st.nextToken()) - 1;
    end = Integer.parseInt(st.nextToken()) - 1;

    cost[start] = 0;
    pq.add(new Node(start, 0));

    while (!pq.isEmpty()) {
      int index = pq.peek().vertex;
      int value = pq.peek().weight;
      pq.poll();

      if (cost[index] < value) {
        continue;
      }

      for (int i = 0; i < al.get(index).size(); ++i) {
        int next = al.get(index).get(i).vertex;
        int nextValue = al.get(index).get(i).weight;

        if (nextValue + cost[index] < cost[next]) {
          cost[next] = nextValue + cost[index];
          pq.add(new Node(next, cost[next]));
        }
      }
    }

    bw.write(cost[end] + "\n");
    bw.close();
  }

  public static class Node {
    int vertex;
    int weight;

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