1916 최소비용 구하기

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

1916번: 최소비용 구하기

문제 접근

도시와 버스의 관계를 묵시적 그래프로 나타낼 수 있고 그래프 탐색 방법으로 문제의 답을 도출할 수 있다.

시간제한이 짧고, 도시의 개수와 버스의 개수가 많기 때문에 그리디한 방법을 사용해야 한다.

즉, 가장 짧은 엣지부터 방문하고, 이미 짧은 경로를 알고 있다면 이후의 노드들은 탐색하지 않아야 한다.

우선순위 큐를 사용하여 가장 짧은 cost의 엣지부터 방문하도록 하는게 포인트다.

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

public class Main {
  public static int N, M, Start, End, MAX_V = 1000 * 100000 + 1;
  public static HashMap<Integer, HashMap<Integer, Integer>> graph = new HashMap<>();
  public static int dijkstra(){
    int[] dist = new int[N + 1];
    for(int i = 0; i < dist.length; i++)
      dist[i] = MAX_V;
    Queue<int[]> pq = new PriorityQueue<>((a1, a2) -> {
      if(a1[0] == a2[0])
        return a1[1] - a2[1];
      return a1[0] - a2[0];
    });
    pq.add(new int[]{0, Start});
    dist[Start] = 0;
    while(!pq.isEmpty()){
      int[] temp = pq.poll();
      int cost = temp[0];
      int cur = temp[1];
      if(dist[cur] < cost)
        continue;

      for(Integer next : graph.get(cur).keySet()){
        int nextCost = dist[cur] + graph.get(cur).get(next);
        if(dist[next] > nextCost){
          dist[next] = nextCost;
          pq.add(new int[]{nextCost, next});
        }
      }
    }
    return dist[End];
  }
  public static void main(String[] args) throws Exception {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st = new StringTokenizer(br.readLine());
    N = Integer.parseInt(st.nextToken());
    st = new StringTokenizer(br.readLine());
    M = Integer.parseInt(st.nextToken());
    int from, to, dist;
    for(int i = 1; i <= N; i++)
      graph.put(i, new HashMap<>());
    for(int i = 0; i < M; i++){
      st = new StringTokenizer(br.readLine());
      from = Integer.parseInt(st.nextToken());
      to = Integer.parseInt(st.nextToken());
      dist = Integer.parseInt(st.nextToken());
      if(graph.get(from).containsKey(to)){
        if(graph.get(from).get(to) > dist){
          graph.get(from).put(to, dist);
        }
      }
      else{
        graph.get(from).put(to, dist);
      }
    }
    st = new StringTokenizer(br.readLine());
    Start = Integer.parseInt(st.nextToken());
    End = Integer.parseInt(st.nextToken());
    int answer = dijkstra();
    System.out.println(answer);
  }
}