BJ 1753最短経路
21833 ワード
https://www.acmicpc.net/problem/1753
これは古典的なマルチアウトプットアルゴリズムの問題である.
多芸団の過程.
1.出発点の設定
2.出発点に関連する頂点までの最小距離
3.アクセスされていない頂点で最もコストの低い頂点を選択
4.頂点の処理にアクセスし、頂点を通過したときに最小距離を更新する
5.アクセスが完了するまで、すべての3~4つのプロセスを繰り返します.
キューを使用して条件が適切な場合は、キューに追加して行えばよい.
これは古典的なマルチアウトプットアルゴリズムの問題である.
多芸団の過程.
1.出発点の設定
2.出発点に関連する頂点までの最小距離
3.アクセスされていない頂点で最もコストの低い頂点を選択
4.頂点の処理にアクセスし、頂点を通過したときに最小距離を更新する
5.アクセスが完了するまで、すべての3~4つのプロセスを繰り返します.
キューを使用して条件が適切な場合は、キューに追加して行えばよい.
package day0224;
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
public class ShortestRoute {
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
static StringTokenizer st;
static class Node implements Comparable<Node>{
int to, w;
public Node(int to, int w) {
this.to = to;
this.w = w;
}
@Override
public int compareTo(Node o) {
// TODO Auto-generated method stub
return w - o.w;
}
}
public static void main(String[] args) throws IOException {
st = new StringTokenizer(br.readLine());
int V = Integer.parseInt(st.nextToken());
int E = Integer.parseInt(st.nextToken());
ArrayList<Node>[] adjList = new ArrayList[V];
for(int i = 0; i < V; i++) {
adjList[i] = new ArrayList<>();
}
int start = Integer.parseInt(br.readLine()) - 1;
for (int i = 0; i < E; i++) {
st = new StringTokenizer(br.readLine());
int from = Integer.parseInt(st.nextToken()) - 1;
int to = Integer.parseInt(st.nextToken()) - 1;
int w = Integer.parseInt(st.nextToken());
adjList[from].add(new Node(to, w));
}
int[] dist = new int[V];
boolean[] visited = new boolean[V];
Arrays.fill(dist, Integer.MAX_VALUE);
dist[start] = 0;
PriorityQueue<Node> q = new PriorityQueue<>();
q.add(new Node(start, 0));
while(!q.isEmpty()) {
Node curNode = q.poll();
if(visited[curNode.to] == true) {
continue;
}
visited[curNode.to] = true;
for(Node nd : adjList[curNode.to]) {
if(dist[curNode.to] + nd.w < dist[nd.to]) {
dist[nd.to] = dist[curNode.to] + nd.w;
q.add(new Node(nd.to, dist[nd.to]));
}
}
}
for (int i = 0; i < V; i++) {
if(dist[i] == Integer.MAX_VALUE) bw.append("INF\n");
else bw.append(dist[i] + "\n");
}
bw.flush();
}
}
Reference
この問題について(BJ 1753最短経路), 我々は、より多くの情報をここで見つけました https://velog.io/@mraz0210/BJ1753-최단경로-다익스트라テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol