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

최단경로 문제!

start 와 end가 나와있어서 그 경로로 가는 최소 경로를 출력하면 되는 문제였다.

바로 방금 푼 최단경로 문제와 똑같이 dijkstra로 풀었다.

---

package 최소비용구하기;

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

class Node implements Comparable<Node> {

	private int index;
	private int distance;

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

	public int getIndex() {
		return this.index;
	}

	public int getDistance() {
		return this.distance;
	}

	// 거리(비용)가 짧은 것이 높은 우선순위를 가지도록 설정
	@Override
	public int compareTo(Node other) {
		if (this.distance < other.distance) {
			return -1;
		}
		return 1;
	}
}

public class Main {

	public static final int INF = (int) 1e9; // 무한을 의미하는 값으로 10억을 설정
	public static int n, m, start,end;
	// 각 노드에 연결되어 있는 노드에 대한 정보를 담는 배열
	public static ArrayList<ArrayList<Node>> graph = new ArrayList<ArrayList<Node>>();
	// 최단 거리 테이블 만들기
	public static int[] d = new int[100001];
	public static void dijkstra(int start) {
		PriorityQueue<Node> pq = new PriorityQueue<>();
		//시작 노드로 가기 위한 최단 경로 0
		pq.offer(new Node(start,0));
		d[start] = 0;
		while(!pq.isEmpty()) {
			//가장 최단 거리가 짧은 노드에 대한 정보 꺼내기
			Node node = pq.poll();
			int dist = node.getDistance(); //현재 노드까지의 비용
			int now = node.getIndex(); //현재 노드
			
			//이미 처리한적이 있으면 무시
			if(d[now] < dist) continue;
			for(int i = 0; i < graph.get(now).size(); i++) {
				
				int cost = d[now] + graph.get(now).get(i).getDistance();
				//현재 노드를 거쳐서, 다른 노드로 이동하는 거리가 더 짧은 경우
				if(cost < d[graph.get(now).get(i).getIndex()]) {
					d[graph.get(now).get(i).getIndex()] = cost;
					pq.offer(new Node(graph.get(now).get(i).getIndex(), cost));
				}
			}
		}
	}
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		n = scan.nextInt();
		m = scan.nextInt();
		
		for(int i = 0; i <= n; i++) {
			graph.add(new ArrayList<Node>());
		}
		
		for(int i = 0; i < m; i++) {
			int u = scan.nextInt();
			int v = scan.nextInt();
			int w = scan.nextInt();
			
			graph.get(u).add(new Node(v,w));
		}
		
		start = scan.nextInt();
		end = scan.nextInt();
		
		//최단 거리 테이블을 무한으로 초기화
		Arrays.fill(d,INF);
		
		dijkstra(start);
		
		System.out.println(d[end]);
		
		scan.close();
	}
}