1753_최단경로

사용 알고리즘: 데이크스트라

사용 언어: java

 

package ssafyAlgorithm;

import java.io.*;
import java.util.*;

public class Main_bj_1753_최단경로 {
	static int v,e, dp[];
	static ArrayList<int[]>[] al;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		v = sc.nextInt(); //정점 개수
		e = sc.nextInt(); //간선 개수
		int start = sc.nextInt(); //시작 정점의 번호
		
		al = new ArrayList[v+1];
		for (int i = 0; i < v+1; i++) {
			al[i] = new ArrayList<>();
		}
		
		for (int i = 0; i < e; i++) {
			int s = sc.nextInt();
			int e = sc.nextInt();
			int w = sc.nextInt();
			
			al[s].add(new int[] {e, w});
		}
		//입력 끝
		
		dp = new int[v+1];
		Arrays.fill(dp, Integer.MAX_VALUE);
		dp[start] = 0; //자기 자신은 0
		dijkstra_1753(start);
		
		//답 출력
		for (int i = 1; i < v+1; i++) {
			if(dp[i] != Integer.MAX_VALUE)
				System.out.println(dp[i]);
			else
				System.out.println("INF");
		}
	}

	private static void dijkstra_1753(int start) {
		PriorityQueue<int[]> pq = new PriorityQueue<>((o1, o2) -> o1[1] - o2[1]);
		pq.add(new int[] {start,0});
		
		while(!pq.isEmpty()) {
			int[] cur = pq.poll(); //노드, 걸린 거리
			
			for(int[] nxt : al[cur[0]]) {
				int 다음노드 = nxt[0];
				int 거리 = nxt[1];
				
				if(dp[다음노드] > 거리+cur[1]) {
					dp[다음노드] = 거리+cur[1];
					pq.add(new int[] {다음노드, 거리+cur[1]});
				}
			}
		}
	}

}

 

데이크스트라!!

단방향에, 가중치가 서로 다름, 바로 갈 수 없는 곳도 있으니까 dp로 갱신해가며 찾아야 함