[BAEKJOON] 플로이드

---

하나의 출발점에 대해 모든 정점의 최단 경로를 구한 다음, 문제에서 요구하는 도착점까지의 최단 경로를 출력한다.

 

다익스트라 알고리즘으로 풀이

1. 모든 정점의 비용을 최댓값으로 초기화한다. (시작점의 비용은 0)

2. 최단 경로여야 하므로 우선순위큐를 사용하여 비용이 오름차순 정렬되게끔 한다. (작은 비용의 경로먼저 탐색)

3. 탐색해야 할 노드의 비용이 현재까지 지나온 비용보다 클 경우는 탐색할 필요 없음

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

public class Main {
	static int N;
	static ArrayList<ArrayList<Node>> arr;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		N = Integer.parseInt(br.readLine());
		int M = Integer.parseInt(br.readLine());
		arr = new ArrayList<>();
		for (int i = 0; i < N; i++) {
			arr.add(new ArrayList<>());
		}
		for (int i = 0; i < M; i++) {
			st = new StringTokenizer(br.readLine());
			int from = Integer.parseInt(st.nextToken()) - 1;
			int to = Integer.parseInt(st.nextToken()) - 1;
			int weight = Integer.parseInt(st.nextToken());
			arr.get(from).add(new Node(to, weight));
		}
		st = new StringTokenizer(br.readLine());
		System.out.println(dijkstra(Integer.parseInt(st.nextToken()) - 1, Integer.parseInt(st.nextToken()) - 1));
	}

	private static int dijkstra(int start, int end) {
		int[] dist = new int[N];
		boolean[] visit = new boolean[N];
		Arrays.fill(dist, Integer.MAX_VALUE);
		PriorityQueue<Node> q = new PriorityQueue<>((a, b) -> Integer.compare(a.weight, b.weight));
		q.offer(new Node(start, 0));
		dist[start] = 0;
		while (!q.isEmpty()) {
			Node now = q.poll();
			int node = now.node;
			if (visit[node])
				continue;
			visit[node] = true;
			for (int i = 0; i < arr.get(node).size(); i++) {
				Node nextNode = arr.get(node).get(i);
				if (dist[nextNode.node] > nextNode.weight + dist[node]) {
					dist[nextNode.node] = nextNode.weight + dist[node];
					q.offer(new Node(nextNode.node, dist[nextNode.node]));
				}
			}
		}
		return dist[end];
	}

	public static class Node {
		int node, weight;

		public Node(int node, int weight) {
			super();
			this.node = node;
			this.weight = weight;
		}
	}
}

[출처]

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

1916번: 최소비용 구하기