그래프 알고리즘 예제(5). 백준 [1916] 최소비용 구하기

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

지난 포스트에 풀었던 다익스트라 알고리즘을 다른 문제로 다시 풀어 보았다.
저번의 실수를 만회하기위해 어제 틀린 부분을 집중해서 풀어보았다.

1트만에 맞았다 ㅎㅎㅎㅎ
0.5초라 시간 초과가 뜨지 않을까 했는데 다행히 뜨지 않았다.

지난 포스트에서는 모든 노드까지의 최단거리를 구하는 것인데 이번 문제는 그냥 도착 노드까지의 최소 비용만 구하면 된다. 즉, 도착 노드의 최소 비용만 출력하면 된다.

 

다음은 Java로 작성한 코드이다.

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

public class MinimumCost {

	public static void main(String[] args) {
		//도착지, 가중치 저장 자료구조
		class Pair implements Comparable<Pair>{
			int a;
			int b;
			public Pair(int a, int b) {
				this.a = a;
				this.b = b;
			}

			public int getA() {
				return a;
			}
			public int getB() {
				return b;
			}

			@Override
			public int compareTo(Pair o) {
				return this.b - o.getB();
			}
		}
		
		final int INF = 987654321;
		Scanner scan = new Scanner(System.in);
		//도시 수
		int city = scan.nextInt();
		//버스 수
		int bus = scan.nextInt();
		
		//거리 저장 배열
		int[] distance = new int[city+1];
		
		//방문 여부 저장 배열
		boolean[] visited = new boolean[city+1];
		
		//그래프
		ArrayList<ArrayList<Pair>> graph = new ArrayList<ArrayList<Pair>>();
		
		
		//초기화
		for (int i = 0; i <= city; i++) {
			graph.add(new ArrayList<Pair>());
		}
		
		for (int i = 0; i <= city; i++) {
			visited[i] = false;
			distance[i] = INF;
		}
		
		for (int i = 0; i < bus; i++) {
			graph.get(scan.nextInt()).add(new Pair(scan.nextInt(), scan.nextInt()));
		}
		
		//시작 노드, 도착 노드
		int startnode = scan.nextInt();
		int endnode = scan.nextInt();
		
		//시작 노드 거리 초기화 및 우선순위 큐
		distance[startnode] = 0;
		PriorityQueue<Pair> q = new PriorityQueue<Pair>();
		q.add(new Pair(startnode, 0));
		
		//다익스트라
		while(!q.isEmpty()) {
			int a = q.poll().getA();
			
			if(visited[a]) {
				continue;
			}
			
			visited[a] = true;
			for(Pair p : graph.get(a)) {
				int b = p.getA();
				int w = p.getB();
				
				if(distance[b] > distance[a] + w) {
					distance[b] = distance[a] + w;
					q.add(new Pair(b, distance[b]));
				}
			}
		}
		
		//출력
		System.out.print(distance[endnode]);
	}

}