[다익스트라] 최소비용구하기(백준 1916번, 자바)☆☆☆

 

다익스트라 알고리즘 .............

 

- 가중치가 작은 순으로 정점 정렬(우선 순위 큐 사용)

- 버스의 비용이 0인 경우도 있음 (즉, map[v.no,i] 값이 0 이어도 이동 가능)

--> 따라서, map 배열을 0이 아닌 Integer.MAX_VALUE 로 초기화 

 

package week7;

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

public class Main {

	static class Vertex implements Comparable<Vertex>{
		int no;
		long weight;

		public Vertex(int no, long weight) {
			super();
			this.no = no;
			this.weight = weight;
		}
		@Override
		public int compareTo(Vertex o) {
			// TODO Auto-generated method stub
			return Long.compare(this.weight, o.weight);
		}	
	}
	
	static int N,M;
	static int[][] map;
	static boolean[] visit;
	static long[] distance;
	static int start, dest;
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		M = Integer.parseInt(br.readLine());
		
		map=new int[N+1][N+1];
		visit=new boolean[N+1];
		distance=new long[N+1];
		
		for(int i=1;i<=N;i++) {
			Arrays.fill(map[i], Integer.MAX_VALUE);
		}
		
		for(int i=0;i<M;i++) {
			
		 	StringTokenizer st=new StringTokenizer(br.readLine());
			int x=Integer.parseInt(st.nextToken());
			int y=Integer.parseInt(st.nextToken());
			int d=Integer.parseInt(st.nextToken());
			
		
			if(map[x][y]>d) map[x][y]=d;
			
		}
		StringTokenizer st=new StringTokenizer(br.readLine());
		
		start=Integer.parseInt(st.nextToken());
		dest=Integer.parseInt(st.nextToken());
		
		final int INF=Integer.MAX_VALUE;
		
		Arrays.fill(distance, INF);
		distance[start]=0;
		
		PriorityQueue<Vertex> pq=new PriorityQueue<>();
		
		pq.offer(new Vertex(start, distance[start]));
	
	
		while(!pq.isEmpty()) {
			Vertex v=pq.poll();
			if(visit[v.no]) continue; 
			visit[v.no]=true;
			if(v.no==dest) break; 
			 
			for(int i=1;i<=N;i++) {
				if(!visit[i] && map[v.no][i] !=Integer.MAX_VALUE && map[v.no][i]+ v.weight < distance[i]){
					distance[i]=map[v.no][i]+v.weight;
					pq.offer(new Vertex(i, distance[i]));
				}
			}
		}
		
		System.out.println(distance[dest]);
		

	}

}