白駿1753:最短パス

質問する
方向図が与えられている場合は、指定された開始点から他のすべての頂点への最短パスを解くプログラムを作成します.ただし、すべての幹線の重み付けは10以下の自然数です.
入力
第1行は頂点の個数Vと幹線の個数Eを与える.(1≦V≦20000,1≦E≦300000)すべての頂点が1〜Vの番号であると仮定する.2行目には、開始点の番号K(1≦K≦V)が与えられる.3行目から、各幹線を表す3つの整数(u,v,w)が順次与えられる.これはuからvまでの重み付けwの幹線が存在することを意味する.uとvは異なり,wは10以下の自然数である.異なる2つの頂点の間に複数の幹線が存在する可能性があることに注意してください.
しゅつりょく
最初の行からV行にまたがり、最初の行からi番頂点への最短パスのパス値を出力します.始点自体の出力はゼロであり、経路が存在しない場合はINFを出力すればよい
BOJ1753
に近づく
これは最短経路アルゴリズムで知られる多出口アルゴリズムの編成の問題である.以前に関連項目を行ったことがありますが、調べてみると思い出しました.
マルチアウトアルゴリズムは、重み付け図で使用される開始ノードから残りのノードへの最短パスを検索するアルゴリズムである.主な過程は以下の通りである.
1.dist配列を作成し、最大値に初期化します.(始点からiノードまでの最短パスを格納する配列)
2.始点のdist値を0に設定し、始点に関連するノードのdistを2つのノード間の距離に設定します.
3.非アクセスノードのdist値が最も小さいノードを検索します.
4.ノードにアクセスし、ノードのdist値が前のノードのdist値+重み付け値より大きい場合は、この値に設定します.
5.すべてのノードにアクセスするまで繰り返します.
アルゴリズムは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 {
	public static class Edge implements Comparable<Edge> {
		public int v;
		public int Weight;
		
		public Edge(int x, int y) {
			this.v = x;
			this.Weight = y;
		}

		@Override
		public int compareTo(Edge o) {
			return this.Weight - o.Weight;
		}
	}

	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		String str = bf.readLine();
		StringTokenizer st = new StringTokenizer(str);
		int v = Integer.parseInt(st.nextToken());
		int e = Integer.parseInt(st.nextToken());
		int k = Integer.parseInt(bf.readLine());
		
		ArrayList<ArrayList<Edge>> graph = new ArrayList<>();
		for(int i = 0; i <= v; i++)
			graph.add(new ArrayList<Edge>());
		
		for(int i = 0; i<e; i++) {
			str = bf.readLine();
			st = new StringTokenizer(str);
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			int c = Integer.parseInt(st.nextToken());
			
			graph.get(a).add(new Edge(b, c));
		}
		
		int [] dist = new int[v+1];
		boolean [] check = new boolean[v+1];
		
		Arrays.fill(dist, Integer.MAX_VALUE);
			
		PriorityQueue <Edge> pq = new PriorityQueue<Edge>();
		dist[k] = 0;
		pq.add(new Edge(k, 0));
		
		while(!pq.isEmpty()) {
			Edge now = pq.poll();
			int des = now.v;
			if(check[des])
				continue;
			
			check[des] = true;
			for(int i = 0; i < graph.get(des).size(); i++) {
				if(dist[graph.get(des).get(i).v] >= dist[des] + graph.get(des).get(i).Weight) {
					dist[graph.get(des).get(i).v] = dist[des] + graph.get(des).get(i).Weight;
					pq.add(new Edge(graph.get(des).get(i).v, dist[graph.get(des).get(i).v]));
				}
			}	
		}
		for(int i = 1; i <= v; i++) {
			if(dist[i] == Integer.MAX_VALUE)
				System.out.println("INF");
			else
				System.out.println(dist[i]);
		}
	}
}