BJ 1753最短経路


https://www.acmicpc.net/problem/1753
これは古典的なマルチアウトプットアルゴリズムの問題である.
多芸団の過程.
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();
	}
}