[백준] 1916 최소비용 구하기 - JAVA

1. 문제 유형 : MST, 다익스트라

2. 시간복잡도 : O(ElogE)

• O(E) : 모든 간선 탐색
• O(logE) : 우선순위 큐의 연산

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {

	static class Node {
		int v, weight;
		Node link;

		public Node(int v, int weight, Node link) {
			super();
			this.v = v;
			this.weight = weight;
			this.link = link;
		}
	}

	static class Vertex implements Comparable<Vertex> {
		int no, minDistance;

		public Vertex(int no, int minDistance) {
			super();
			this.no = no;
			this.minDistance = minDistance;
		}
		
		@Override
		public int compareTo(Vertex o) {
			return this.minDistance - o.minDistance;
		}
	}

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(in.readLine());
		int M = Integer.parseInt(in.readLine());

		Node[] matrix = new Node[N + 1];
		StringTokenizer st = null;
		for (int i = 0; i < M; i++) {
			st = new StringTokenizer(in.readLine());
			int start = Integer.parseInt(st.nextToken());
			int end = Integer.parseInt(st.nextToken());
			int weight = Integer.parseInt(st.nextToken());
			matrix[start] = new Node(end, weight, matrix[start]);
		}

		st = new StringTokenizer(in.readLine());
		int from = Integer.parseInt(st.nextToken());
		int to = Integer.parseInt(st.nextToken());
		PriorityQueue<Vertex> pq = new PriorityQueue<>();
		boolean[] visited = new boolean[N + 1];
		int[] distance = new int[N + 1];
		Arrays.fill(distance, Integer.MAX_VALUE);
		
		pq.offer(new Vertex(from, 0));
		distance[from] = 0;

		while(!pq.isEmpty()) {
			Vertex v = pq.poll();
			if(visited[v.no]) continue;
			
			visited[v.no] = true;
			for (Node current=matrix[v.no]; current != null; current = current.link) {
				if(!visited[current.v] && distance[current.v] > distance[v.no]+current.weight) {
					distance[current.v] = distance[v.no]+current.weight;
					pq.offer(new Vertex(current.v, distance[current.v]));
				}
			}
			if(v.no == to) break;
		}
		
		System.out.println(distance[to]);
		
	}

}