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

📌 문제

N개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 M개의 버스가 있다. 우리는 A번째 도시에서 B번째 도시까지 가는데 드는 버스 비용을 최소화 시키려고 한다. A번째 도시에서 B번째 도시까지 가는데 드는 최소비용을 출력하여라. 도시의 번호는 1부터 N까지이다.

✔ 접근방법

특정한 노드에서 출발하여 다른 노드로 가는 최단경로를 계산하고, 음의 간선이 없기 때문에 다익스트라를 사용한다.
다익스트라 구현시, 우선순위 큐 자료구조를 사용하면 비용이 짧은 값을 계산하는 과정을 생략할 수 있다.

✔ 코드

import java.util.ArrayList;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.Scanner;

//최소비용 구하기
//다익스트라 알고리즘
class Node implements Comparable<Node> {
	int y;
	int distance;

	public Node(int y, int distance) {
		this.y = y;
		this.distance = distance;
	}

	@Override
	public int compareTo(Node arg0) {
		if (this.distance < arg0.distance)
			return -1;
		return 1;
	}
}
public class Main {
	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);
		PriorityQueue<Node> pq = new PriorityQueue<>();
		int n = sc.nextInt();
		int m = sc.nextInt();
		ArrayList<ArrayList<Node>> graph = new ArrayList<>();
		
		//최단거리 테이블
		int[] d = new int[n];
		int INF = (int)1e9;
		
		Arrays.fill(d, INF);
		

		//그래프 초기화
		for (int i = 0; i < n; i++) {
			graph.add(new ArrayList<Node>());
		}

		for (int i = 0; i < m; i++) {
			int x = sc.nextInt()-1;
			int y = sc.nextInt()-1;
			int distance = sc.nextInt();
			graph.get(x).add(new Node(y, distance));
		}
		
		int start = sc.nextInt()-1;
		int end = sc.nextInt()-1;
		
		pq.add(new Node(start, 0));
		d[start] = 0;
		
		while(!pq.isEmpty()) {
			Node node = pq.poll();
			int distance = node.distance;
			int index = node.y;
			
			if(d[index] < distance) continue;
			
			for(int i = 0; i < graph.get(index).size(); i++) {
				int cost = d[index] + graph.get(index).get(i).distance;
				if(cost < d[graph.get(index).get(i).y]) {
					d[graph.get(index).get(i).y] = cost;
					pq.offer(new Node(graph.get(index).get(i).y, cost));
				}
				
			}
		}
		
		System.out.println(d[end]);
	}
}

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