방향그래프가 주어지면 주어진 시작점에서 다른 모든 정점으로의 최단 경로를 구하는 프로그램을 작성하시오. 단, 모든 간선의 가중치는 10 이하의 자연수이다.
첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 주어진다. 셋째 줄부터 E개의 줄에 걸쳐 각 간선을 나타내는 세 개의 정수 (u, v, w)가 순서대로 주어진다. 이는 u에서 v로 가는 가중치 w인 간선이 존재한다는 뜻이다. u와 v는 서로 다르며 w는 10 이하의 자연수이다. 서로 다른 두 정점 사이에 여러 개의 간선이 존재할 수도 있음에 유의한다.
입력 | 출력 |
---|---|
5 6 | 0 |
1 | 2 |
5 1 1 | 3 |
1 2 2 | 7 |
1 3 3 | INF |
2 3 4 | |
2 4 5 | |
3 4 6 |
다익스트라 알고리즘
배열로 하니까 메모리 오류 → 리스트로
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class four1754 {
public void solution() throws IOException {
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer infoToken = new StringTokenizer(reader.readLine());
int nodeCnt = Integer.parseInt(infoToken.nextToken());
int edgeCnt = Integer.parseInt(infoToken.nextToken());
int startNode = Integer.parseInt(reader.readLine()) - 1;
List<List<int[]>> adjList = new ArrayList<>();
for (int i = 0; i < nodeCnt; i++) {
adjList.add(new ArrayList<>());
}
for (int i = 0; i < edgeCnt; i++) {
StringTokenizer edgeToken = new StringTokenizer(reader.readLine());
int from = Integer.parseInt(edgeToken.nextToken()) - 1;
int to = Integer.parseInt(edgeToken.nextToken()) - 1;
int cost = Integer.parseInt(edgeToken.nextToken());
adjList.get(from).add(new int[]{to, cost});
}
boolean[] visited = new boolean[nodeCnt];
int[] dist = new int[nodeCnt];
Arrays.fill(dist, Integer.MAX_VALUE);
dist[startNode] = 0;
PriorityQueue<int[]> minHeap = new PriorityQueue<>(
Comparator.comparingInt(o -> o[1])
);
minHeap.offer(new int[] {startNode, 0});
while(!minHeap.isEmpty()) {
int[] current = minHeap.poll();
if(visited[current[0]]) continue;
visited[current[0]] = true;
for (int[] neighbor: adjList.get(current[0])) {
int neighborVertex = neighbor[0];
int neighborCost = neighbor[1];
if(!visited[neighborVertex] &&
dist[neighborVertex] > current[1] + neighborCost) {
dist[neighborVertex] = current[1] + neighborCost;
minHeap.offer(new int[] {neighborVertex, dist[neighborVertex]});
}
}
}
for (int distance:dist) {
if (distance == 2147483647) System.out.println("INF");
else System.out.println(distance);
}
}
public static void main(String[] args) throws IOException {
new four1754().solution();
}
}