[JAVA] 백준 5996 - Heat Wave

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

정점의 개수와 양방향 간선의 개수, 시작점과 끝점이 주어졌을 때 최소 이동 비용을 구하는 문제이다.

정점의 개수 만큼 weight를 저장하는 배열과 {목적지, 비용}을 저장하는 클래스를 선언하고

우선순위큐에 {정점번호, 시작점에서 도달할 때 드는 비용}을 저장하며 다익스트라를 수행했다.

 

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int[] arr = getArray(br.readLine());
        int nodeCount = arr[0];
        int vertexCount = arr[1];
        int startNode = arr[2];
        int endNode = arr[3];
        int[] nodeList = new int[nodeCount+1];
        Arrays.fill(nodeList,Integer.MAX_VALUE/3);
        nodeList[startNode] = 0;
        List<Duo>[] vertexList = new List[nodeCount+1];
        for (int i = 0; i <= nodeCount; i++) {
            vertexList[i] = new ArrayList<>();
        }

        for (int i = 0; i < vertexCount; i++) {
            int[] info = getArray(br.readLine());
            vertexList[info[0]].add(new Duo(info[1],info[2]));
            vertexList[info[1]].add(new Duo(info[0],info[2]));
        }
        boolean[] visited = new boolean[nodeCount+1];
        PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(x -> x[1]));
        pq.offer(new int[]{startNode, nodeList[startNode]});
        while(!pq.isEmpty()){
            int[] temp = pq.poll();
            int value = temp[0];
            int weight = temp[1];
            List<Duo> vertex = vertexList[value];
            if(visited[value]) continue;
            visited[value] = true;
            for (int i = 0; i < vertex.size(); i++) {
                Duo d = vertex.get(i);
                if(weight+d.weight < nodeList[d.to]){
                    nodeList[d.to] = weight+d.weight;
                    pq.offer(new int[]{d.to, nodeList[d.to]});
                }
            }
        }

        System.out.println(nodeList[endNode]);
    }
    static int par(String s) {
        return Integer.parseInt(s);
    }

    static int[] getArray(String s) {
        return Arrays.stream(s.split(" ")).mapToInt(Integer::parseInt).toArray();
    }
}

class Duo{
    int to;
    int weight;
    Duo(int t, int w){
        this.to = t;
        this.weight = w;
    }
}