백준 1916 Java

문제

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

알고리즘 설명

다익스트라는 그래프에서 최소 비용을 구하는 알고리즘이다.
route 값이 양의 가중치 일때만 사용가능하다.
탐색을 하면서 
현재까지 비용 + 이동 비용 < 이동 할 노드의 비용 이면
이동을 하면서 내가 갈 노드 비용을 update 해주면 된다.

비용이 작은 route 순으로 탐색을 해야하기 때문에
Priority Queue 를 이용해서 구현하면 편하다.

생각보다 간단한 알고리즘임

구현 코드

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

public class Main {

	static int N;
	static int R;
	
	static ArrayList<Integer> [] nlist;
	static ArrayList<Integer> [] clist;
	
	static int [] alist;
	
	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		N = Integer.parseInt(br.readLine());
		R = Integer.parseInt(br.readLine());
		
		nlist = new ArrayList [N+1];
		clist = new ArrayList [N+1];
				
		for (int i = 1; i<=N; i++) {
			nlist[i] = new ArrayList<Integer>();
			clist[i] = new ArrayList<Integer>();			
		}
		
		alist = new int [N+1];
		
		for (int i = 1; i<=R; i++) {
			
			StringTokenizer st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			int c = Integer.parseInt(st.nextToken());
			nlist[a].add(b);
			//nlist[b].add(a);
			clist[a].add(c);
			//clist[b].add(c);			
		}
		
		Arrays.fill(alist, 1, N+1, Integer.MAX_VALUE);
				
		PriorityQueue<Integer> q = new PriorityQueue<Integer>(new Compare());
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int start = Integer.parseInt(st.nextToken());
		int end   = Integer.parseInt(st.nextToken());
		
		alist[start] = 0;
		q.add(start);
		
				
		while (!q.isEmpty()) {
			
			int t = q.poll();
			
			for (int i = 0; i<nlist[t].size(); i++) {
				
				int x = nlist[t].get(i);
				
				if (alist[x] > alist[t] + clist[t].get(i)) {
					alist[x] = alist[t] + clist[t].get(i);
					q.add(x);
				}

			}	

		}		
		
		long answer = 0;
		
		if (alist[end] == Integer.MAX_VALUE) {
			answer = -1;
		} else {
			answer = alist[end];
		}
		System.out.println(answer);
		 
		
	}

	
	static class Compare implements Comparator<Integer>{

		@Override
		public int compare(Integer a, Integer b) {
			// TODO Auto-generated method stub
			if (alist[a] < alist[b]) {
				return -1;
			} else if (alist[a] > alist[b]) {
				return 1;
			} else {
				return 0;
			}
		}
		
	}
	

}