[백준 - 5966][GOLD 5][해설 X] - Heat Wave (JAVA)

문제 링크

---

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

 

문제

---

The good folks in Texas are having a heatwave this summer. Their Texas Longhorn cows make for good eating but are not so adept at creating creamy delicious dairy products. Farmer John is leading the charge to deliver plenty of ice cold nutritious milk to Texas so the Texans will not suffer the heat too much.

FJ has studied the routes that can be used to move milk from Wisconsin to Texas. These routes have a total of T (1 <= T <= 2,500) towns conveniently numbered 1..T along the way (including the starting and ending towns). Each town (except the source and destination towns) is connected to at least two other towns by bidirectional roads that have some cost of traversal (owing to gasoline consumption, tolls, etc.). Consider this map of seven towns; town 5 is the source of the milk and town 4 is its destination (bracketed integers represent costs to traverse the route):

                              [1]----1---[3]-
                             /               \
                      [3]---6---[4]---3--[3]--4
                     /               /       /|
                    5         --[3]--  --[2]- |
                     \       /        /       |
                      [5]---7---[2]--2---[3]---
                            |       /
                           [1]------

Traversing 5-6-3-4 requires spending 3 (5->6) + 4 (6->3) + 3 (3->4) = 10 total expenses.

Given a map of all the C (1 <= C <= 6,200) connections (described as two endpoints R1i and R2i (1 <= R1i <= T; 1 <= R2i <= T) and costs (1 <= Ci <= 1,000), find the smallest total expense to traverse from the starting town Ts (1 <= Ts <= T) to the destination town Te (1 <= Te <= T).

 

 입력

---

• Line 1: Four space-separated integers: T, C, Ts, and Te
• Lines 2..C+1: Line i+1 describes road i with three space-separated integers: R1i, R2i, and Ci

 

출력

---

• Line 1: A single integer that is the length of the shortest route from Ts to Te. It is guaranteed that at least one route exists.

 

해결 코드

---

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int T = Integer.parseInt(st.nextToken());
        int C = Integer.parseInt(st.nextToken());
        int Ts = Integer.parseInt(st.nextToken());
        int Te = Integer.parseInt(st.nextToken());

        List<Node> graph[] = new ArrayList[T+1];
        
        //그래프 생성
        for(int i=0;i<=T;i++){
            graph[i] = new ArrayList<>();
        }

        for(int i=0;i<C;i++){
            st = new StringTokenizer(br.readLine());

            int R1 = Integer.parseInt(st.nextToken());
            int R2 = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());

            graph[R1].add(new Node(R2,c));
            graph[R2].add(new Node(R1,c));
        }
    
        //Ts부터 모든 노드간의 최단거리 계산
        int[] shortestDistance = new int[T+1];
        Arrays.fill(shortestDistance,Integer.MAX_VALUE);
        shortestDistance[Ts] = 0;

        PriorityQueue<Node> pq = new PriorityQueue<>((a,b)-> a.distance - b.distance);
        pq.add(new Node(Ts,0));
    
        //다익스트라를 이용해 Ts부터 모든 노드간의 최단거리 연산
        while(!pq.isEmpty()){
            Node curr = pq.poll();

            if(curr.distance > shortestDistance[curr.num]){
                continue;
            }

            for(Node next : graph[curr.num]){
                if(shortestDistance[next.num] > shortestDistance[curr.num] + next.distance){
                    shortestDistance[next.num] = shortestDistance[curr.num] + next.distance;
                    pq.add(new Node(next.num,shortestDistance[next.num]));
                }
            }
        }

        System.out.println(shortestDistance[Te]);
    }
}

class Node {
    int num;
    int distance;

    public Node(int num, int distance){
        this.num = num;
        this.distance = distance;
    }
}

 

 

실행 결과

---

 

팁

---

• 그래프 생성시 양방향인지 단방향인지 확인하자
• 최대값을 확인해 long형을 넘는지 확인하자