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

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

1916번: 최소비용 구하기

 

바로 복습하기!

의도하지 않았지만 내가 다익스트라만 빼고 풀었나보다 남은게 다익스트라네 '_'

 

이전 최단경로처럼 풀면 답은 나오지만 시간 초과가 난다.

PQ에 넣게 되면, A → B로 이동하는 버스 중 최소 비용이 앞으로 오는데,

이전에 먼저 들어간 높은 비용의 방법은 PQ에서 꺼내고

(연결된 도시를 확인하는) 나머지 작업을 생략시키면 된다.

 

[이 부분 추가]

			// 더 최소인 경우가 PQ에 있는 경우
			if(dp[now.idx] < now.cost)
				continue;

 

 

[코드]

package BOJ_1000;

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;

public class boj1916 {
	static class Bus implements Comparable<Bus>{
		int idx, cost;
		
		public Bus(int idx, int cost) {
			this.idx = idx;
			this.cost = cost;
		}

		@Override
		public int compareTo(Bus o) {
			return this.cost - o.cost;
		}
		
	}
	private static int N, M, start, end;
	private static int[] dp;
	private static ArrayList<Bus>[] next;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		N = Integer.parseInt(br.readLine());
		M = Integer.parseInt(br.readLine());
		
		next = new ArrayList[N+1];
		dp = new int[N+1];
		Arrays.fill(dp, Integer.MAX_VALUE);
		
		for(int i=1; i<=N; i++) {
			next[i] = new ArrayList<Bus>();
		}
		
		for(int i=0; i<M; i++) {
			String[] str = br.readLine().split(" ");
			int a = Integer.parseInt(str[0]);
			int b = Integer.parseInt(str[1]);
			int w = Integer.parseInt(str[2]);
			
			next[a].add(new Bus(b,w));
		}
		
		String[] str = br.readLine().split(" ");
		start = Integer.parseInt(str[0]);
		end = Integer.parseInt(str[1]);
		dp[start]=0;
		
		bfs();
		
		bw.write(dp[end]+"");
		bw.flush();
		bw.close();
	}
	
	public static void bfs() {
		PriorityQueue<Bus> pq = new PriorityQueue<>();
		pq.add(new Bus(start, 0));
		
		while(!pq.isEmpty()) {
			Bus now = pq.poll();
			
			// 더 최소인 경우가 PQ에 있는 경우
			if(dp[now.idx] < now.cost)
				continue;
			
			for(Bus next : next[now.idx]) {
				if(dp[next.idx] > now.cost + next.cost) {
					dp[next.idx] = now.cost + next.cost;
					
					if(next.idx==end)
						continue;
					
					pq.add(new Bus(next.idx, dp[next.idx]));
				}
			}
		}
	}
}