[BOJ]1753号最短パス(Java)
2406 ワード
質問する
https://www.acmicpc.net/problem/1753
に答える
始点からすべての頂点への最短経路を解くDijkstraアルゴリズム
マルチカーブアルゴリズムの実装
-始点からアクセスするかどうか、および始点からの最小パス頂点へ移動
-最小パス頂点に移動した後、頂点の距離配列をリセットします(頂点からの最短距離).
グラフィック情報を最初の隣接行列として解いたが,Tekeの大きさが非常に大きいためメモリオーバーフローエラーが発生した.
従って、隣接行列ではなく隣接リストとして実現される.
コード#コード#
import java.util.*;
import java.io.*;
class Element{
int to, weight;
public Element(int to, int weight) {
this.to = to;
this.weight = weight;
}
}
public class Main{
public static void main(String[] args) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
int V = Integer.parseInt(st.nextToken());
int E = Integer.parseInt(st.nextToken());
int K = Integer.parseInt(br.readLine());
List<Element>[] adjList = new ArrayList[V+1];
for(int i =1 ; i < V+1 ; i++) {
adjList[i] = new ArrayList<>();
}
int[] distance = new int[V+1];
boolean[] visited = new boolean[V+1];
for(int i = 0 ; i < E ; i++) {
st = new StringTokenizer(br.readLine(), " ");
int from = Integer.parseInt(st.nextToken());
int to = Integer.parseInt(st.nextToken());
int weight = Integer.parseInt(st.nextToken());
adjList[from].add(new Element(to, weight));
}
Arrays.fill(distance, Integer.MAX_VALUE);
distance[K] = 0;
int min = 0, current = 1;
for(int i =1 ; i <= V ; i++) {
min = Integer.MAX_VALUE;
for(int j =1 ; j <= V ; j++) {
if(!visited[j] && distance[j] < min) {
min = distance[j];
current = j;
}
}
visited[current] = true;
for(int j =0 ; j < adjList[current].size() ; j++) {
if(!visited[adjList[current].get(j).to] && distance[adjList[current].get(j).to] > min+adjList[current].get(j).weight) {
distance[adjList[current].get(j).to] = min+adjList[current].get(j).weight;
}
}
}
for(int i = 1; i <= V ; i++) {
if(distance[i] == Integer.MAX_VALUE) System.out.println("INF");
else System.out.println(distance[i]);
}
}
}
Reference
この問題について([BOJ]1753号最短パス(Java)), 我々は、より多くの情報をここで見つけました https://velog.io/@dot2__/BOJ-1753번-최단경로-Javaテキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol