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

https://www.acmicpc.net/problem/1916

1916번: 최소비용 구하기

 

최단경로랑 같은 문제. input 순서, 출력만 바꾸면 정답

import java.io.*;
import java.util.*;

public class Main {
	static class Vertex implements Comparable<Vertex>{
		int vertex;
		int distance;
		
		public Vertex(int v, int d) {
			this.vertex = v; this.distance = d;
		}
		public void setWDist(int d) {
			this.distance = d;
		}	
		
		@Override
		public int compareTo(Vertex v) {
			if(this.distance > v.distance)
				return 1;
			else
				return -1;
		}
	}
	static class Edge {
		int veretx;
		int weight;
		public Edge(int v, int w) {
			this.veretx = v; this.weight = w;
		}
	}
	public static void main(String[] args) {
		try {
			BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
			int V = Integer.parseInt(br.readLine());
			int E = Integer.parseInt(br.readLine());
			ArrayList<Edge>[] edge = new ArrayList[V+1];
			
			int[] distance = new int[V+1];
			Arrays.fill(distance,  Integer.MAX_VALUE);
			
			for(int i = 1; i<=V; i++) {
				edge[i] = new ArrayList<>();
			}
			
			for(int i = 0; i<E; i++) {
				String[] query = br.readLine().split(" ");
				int u = Integer.parseInt(query[0]);
				int v = Integer.parseInt(query[1]);
				int w = Integer.parseInt(query[2]);
				
				edge[u].add(new Edge(v, w));	
			}

			String[] input = br.readLine().split(" ");
			int start = Integer.parseInt(input[0]);
			int end = Integer.parseInt(input[1]);
			
			distance[start] = 0;
			
			PriorityQueue<Vertex> p = new PriorityQueue<Vertex>();
			
			p.offer(new Vertex(start, distance[start]));
			
			while(!p.isEmpty()) {
				Vertex curr = p.poll();
				if(curr.distance > distance[curr.vertex])
					continue;
				
				for(Edge e : edge[curr.vertex]) {
					if(distance[e.veretx] > curr.distance + e.weight) {
						distance[e.veretx] = curr.distance + e.weight;
						p.offer(new Vertex(e.veretx, distance[e.veretx]));
					}
				}
			}
			
			System.out.println(distance[end]);
		}catch(IOException e) {	
		}
	}
	
}