G1753. 최단경로

문제

제출 코드

• 사용 알고리즘 : 다익스트라

package gold;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

public class G1753_shortestPath {
	static class Node{
		public int to;
		public int weight;

		public Node(int to, int weight){
			this.to = to;
			this.weight = weight;
		}
	}

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] line = br.readLine().split(" ");
		int V = Integer.parseInt(line[0]);
		int E = Integer.parseInt(line[1]);
		int start = Integer.parseInt(br.readLine());

		List<Node>[] list = new LinkedList[V+1];
		for(int i=1; i<=V; i++) list[i] = new LinkedList<>();

		for(int i=0; i<E; i++) {
			line = br.readLine().split(" ");
			int u = Integer.parseInt(line[0]);
			int v = Integer.parseInt(line[1]);
			int w = Integer.parseInt(line[2]);
			list[u].add(new Node(v, w));
		}

		int[] distance = new int[V+1];
		boolean[] visit = new boolean[V+1];

		Arrays.fill(distance, Integer.MAX_VALUE);

		distance[start] = 0;
		int current = 0;

		for(int v=0; v<V; v++) {
			int min = Integer.MAX_VALUE;
			for(int i=1; i<=V; i++) {
				if(!visit[i] && distance[i]<min) {
					min = distance[i];
					current = i;
				}
			}
			visit[current] = true;

			for(Node no : list[current]) {
				if(!visit[no.to] && min+no.weight<distance[no.to]) {
					distance[no.to] = min + no.weight;
				}
			}
		}
		for(int v=1; v<=V; v++) {
			System.out.println(distance[v]==Integer.MAX_VALUE ? "INF" : distance[v]);
		}
	}

}