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

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

1916번: 최소비용 구하기

문제

풀이

풀이 방식은 이전 포스팅과 동일하다.

https://katastrophe.tistory.com/19

[BOJ] 백준 [1753] 최단경로 JAVA

import java.util.*;
import java.io.*;
 
public class Main{
    static int MAX_DIST = Integer.MAX_VALUE;
    static int[] dist;
    static int V,E,start;
    static ArrayList<Node>[] list;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        V = Integer.parseInt(br.readLine()); E = Integer.parseInt(br.readLine());
        dist = new int[V+1];
        Arrays.fill(dist,MAX_DIST);
        list = new ArrayList[V+1];
        for(int i=1;i<=V;i++)
            list[i] = new ArrayList<Node>();
        for(int i=1;i<=E;i++){
            String[] input = br.readLine().split(" ");
            list[Integer.parseInt(input[0])].add(new Node(Integer.parseInt(input[1]),Integer.parseInt(input[2])));
        }
        String[] input = br.readLine().split(" ");
        int start = Integer.parseInt(input[0]); int end = Integer.parseInt(input[1]);
        System.out.println(findShortPath(start,end));
    }
 
    static int findShortPath(int start,int end) {
        PriorityQueue<Node> q = new PriorityQueue<>();
        q.add(new Node(start,0));
        dist[start] = 0;
        while (!q.isEmpty()){
            Node poll = q.poll();
 
            if(dist[poll.node] < poll.weight)
                continue;
 
            for (Node next : list[poll.node]) {
                if(dist[next.node] > dist[poll.node] + next.weight){
                    dist[next.node] = dist[poll.node] + next.weight;
                    q.add(new Node(next.node,dist[next.node]));
                }
            }
        }
        return dist[end];
    }
 
    static class Node implements Comparable<Node>{
        int node;
        int weight;
 
        public Node(int node, int weight) {
            this.node = node;
            this.weight = weight;
        }
        @Override
        public int compareTo(Node o) {
            return this.weight-o.weight;
        }
    }
}