[BOJ] 5972 택배 배송 G5 (JAVA)

---

---

5972번: 택배 배송

문제 이해

농부 현서는 농부 찬홍이에게 택배를 배달해줘야 합니다. 그리고 지금, 갈 준비를 하고 있습니다. 평화롭게 가려면 가는 길에 만나는 모든 소들에게 맛있는 여물을 줘야 합니다. 물론 현서는 구두쇠라서 최소한의 소들을 만나면서 지나가고 싶습니다.

 

농부 현서에게는 지도가 있습니다. N (1 <= N <= 50,000) 개의 헛간과, 소들의 길인 M (1 <= M <= 50,000) 개의 양방향 길이 그려져 있고, 각각의 길은 C_i (0 <= C_i <= 1,000) 마리의 소가 있습니다. 소들의 길은 두 개의 떨어진 헛간인 A_i 와 B_i (1 <= A_i <= N; 1 <= B_i <= N; A_i != B_i)를 잇습니다. 두 개의 헛간은 하나 이상의 길로 연결되어 있을 수도 있습니다. 농부 현서는 헛간 1에 있고 농부 찬홍이는 헛간 N에 있습니다.

 

다음 지도를 참고하세요.

 

농부 현서가 선택할 수 있는 최선의 통로는 1 -> 2 -> 4 -> 5 -> 6 입니다. 왜냐하면 여물의 총합이 1 + 0 + 3 + 1 = 5 이기 때문입니다.

 

농부 현서의 지도가 주어지고, 지나가는 길에 소를 만나면 줘야할 여물의 비용이 주어질 때 최소 여물은 얼마일까요? 

농부 현서는 가는 길의 길이는 고려하지 않습니다.

아이디어

문제를 보자마자 다익스트라 문제임을 알 수 있다.

 

다익스트라 알고리즘을 활용하여 최소 여물을 구한 뒤 값을 출력해준다.

(PriorityQueue를 활용하였다.)

 

코드

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

public class Main {

	static class Node implements Comparable<Node> {
		int end;
		long weight; // 50000*50000 = 2500000000

		Node(int end, long weight) {
			this.end = end;
			this.weight = weight;
		}

		@Override
		public int compareTo(Node o) {
			return Long.compare(this.weight, o.weight);
		}
	}

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
		ArrayList<ArrayList<Node>> adj = new ArrayList<ArrayList<Node>>();
		for(int i=0;i<N;++i) adj.add(new ArrayList<>());
		long[] d = new long[N];
		Arrays.fill(d, Long.MAX_VALUE);
		d[0]=0;
		for (int i = 0; i < M; ++i) {
			st = new StringTokenizer(br.readLine(), " ");
			int from = Integer.parseInt(st.nextToken())-1;
			int to = Integer.parseInt(st.nextToken())-1;
			int val = Integer.parseInt(st.nextToken());
			adj.get(from).add(new Node(to,val));
			adj.get(to).add(new Node(from,val));
		}
		// 다익스트라
		boolean[] isVisited= new boolean[N];
		PriorityQueue<Node> pq= new PriorityQueue<>();
		pq.add(new Node(0,0));
		
		while(!pq.isEmpty()) {
			Node now = pq.poll();
			if(isVisited[now.end]) continue;
			isVisited[now.end]=true;
			for(Node n : adj.get(now.end)) {
				if(isVisited[n.end]) continue;
				if(d[n.end]> d[now.end]+n.weight) {
					d[n.end] = d[now.end]+n.weight;
					pq.add(new Node(n.end, d[n.end]));
				}
			}
		}
		
		System.out.println(d[N-1]);
	}

}

 

 

 

---

Dev_cpdm