BOJ - 1916 ) 최소비용 구하기

---

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

1916번: 최소비용 구하기

---

Dijkstra알고리즘의 기본적인 형태이다. 특정 A번째에서 B번째까지의 최단 경로를 구하기위해서 

 

정수배열에 A번째에서 각 인덱스 번호까지의 최단거리를 갱신시켜주면서 우선순위큐를 비워준다.

 

최단경로가 갱신된다면, 그 때 까지의 누적 경로합을 다시 우선순위큐에 넣어주면서 실행하면된다.

 

 

---

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class 최소비용구하기 {
	public static class node{
		int end, cost;
		public node(int end, int cost) {
			this.end = end;
			this.cost = cost;
		}
	}
	public static void main(String[] args)  throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int n = Integer.parseInt(st.nextToken()); // 도시개수
		 st = new StringTokenizer(br.readLine());
		int m = Integer.parseInt(st.nextToken()); // 버스개수
		
		ArrayList<node> map[] = new ArrayList[n+1];
		for(int i = 1 ; i <= n ; i++) {
			map[i] = new ArrayList<node>();
		}
		
		for(int i = 0 ; i < m ; i++) {
			st = new StringTokenizer(br.readLine());
			int start = Integer.parseInt(st.nextToken());
			int end = Integer.parseInt(st.nextToken());
			int cost = Integer.parseInt(st.nextToken());
			map[start].add(new node(end, cost));
		}
		st = new StringTokenizer(br.readLine());
		int start = Integer.parseInt(st.nextToken());
		int end = Integer.parseInt(st.nextToken());
		int shortest[] = new int[n+1];
		for( int i = 1 ; i <= n ; i++) {
			shortest[i] = 987654321;
		}
		PriorityQueue<node> pq = new PriorityQueue<>(new Comparator<node>() {
			@Override
			public int compare(node o1, node o2) {
				if( o1.cost > o2.cost) return 1;
				else if( o1.cost < o2.cost) return -1;
				else return 0;
			}
		});
		
		pq.add(new node(start,0));
		shortest[start] = 0;
		
		while(!pq.isEmpty()) {
	
			node now = pq.poll(); // 간선이 작은 상태로만 정렬
			int target = now.end;
			int target_cost = now.cost;
			
			if(shortest[target] < target_cost) continue;
			int size = map[target].size();
			for(int i = 0 ; i < size ; i++) {
				
				int next = map[target].get(i).end;
				int next_cost = map[target].get(i).cost;
				
				if(shortest[next] > shortest[target] + next_cost) {
					shortest[next] = shortest[target] + next_cost;
					pq.add(new node(next ,shortest[target] + next_cost ));
				}
			}
		}
		System.out.println(shortest[end]);
	}
}

---