백준 1916 - 최소비용 구하기

문제

 

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

1916번: 최소비용 구하기

 

 

풀이

 

특정 정점에서 모든 정점까지의 최소 거리를 구하는 문제이므로, 다익스트라 알고리즘을 이용하는 문제이다.

 

https://blog.naver.com/ksw85273/221496288449

다익스트라 알고리즘

 

우선순위 큐를 이용해서 다익스트라 알고리즘을 만든다. 현재 도시와 연결된 도시들을 우선순위큐에 저장하는데 비용을 기준으로 오름차순 저장을 한다. 그러면 현재 도시에서 최소 비용으로 갈 수 있는 다음 도시가 우선수위 큐의 top에 저장이된다. 이때 아직 방문하지 않은 도시이면서, 그 도시로 가는 비용이 이미 설정된 비용보다 작을 경우에만 우선순위 큐에 저장을 해야 한다.

 

1. 우선순위 큐에서 top을 꺼냄 (이번에 방문할 도시)

2. 연결된 도시들 중에 방문을 안했고 가는 비용이 더 적은 도시를 우선순위 큐에 저장

3. 비용 업데이트

4. 우선순위 큐가 빌 때까지 1, 2, 3 반복

 

 

코드

 

python

import heapq
 
n = int(input())
m = int(input())
INF = int(1e9)
 
graph = [[] for _ in range(n+1)]
dist = [INF] * (n + 1)
 
for _ in range(m):
    a, b, c = map(int, input().split())
    graph[a].append((b, c))
 
def dijkstra(start):
    q = []
    heapq.heappush(q, (0, start))
    dist[start] = 0
    while q:
        distance, now = heapq.heappop(q)
        if dist[now] < distance:
            continue
        for i in graph[now]:
            cost = distance + i[1]
            if cost < dist[i[0]]:
                dist[i[0]] = cost
                heapq.heappush(q, (cost, i[0]))
 
start, end = map(int, input().split())
 
dijkstra(start)
print(dist[end]) 
 

 

java

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Scanner;
 
public class Main {
 
    static int n, m;
    static int start, end;
    static List<List<Node>> graph;
    static int[] dist;
 
    public static void main(String[] args) {
        input();
        dijkstra(start);
        System.out.println(dist[end]);
    }
 
    private static void dijkstra(int start) {
        PriorityQueue<Node> pq = new PriorityQueue<>();
        dist[start] = 0;
        pq.offer(new Node(start, 0));
 
        while (!pq.isEmpty()) {
            Node cur = pq.poll();
            int distance = cur.weight;
            int now = cur.end;
 
            if (dist[now] < distance)
                continue;
 
            for (Node next : graph.get(now)) {
                int nextNode = next.end;
                int cost = distance + next.weight;
 
                if (cost < dist[nextNode]) {
                    dist[nextNode] = cost;
                    pq.offer(new Node(nextNode, cost));
                }
            }
        }
    }
 
    private static void input() {
        Scanner sc = new Scanner(System.in);
 
        n = sc.nextInt();
        m = sc.nextInt();
        dist = new int[n + 1];
 
        int INF = (int) 1e9;
        Arrays.fill(dist, INF);
 
        graph = new ArrayList<>();
        for (int i=0; i<=n; i++) {
            graph.add(new ArrayList<>());
        }
        for (int i=0; i<m; i++) {
            int a, b, c;
            a = sc.nextInt();
            b = sc.nextInt();
            c = sc.nextInt();
            graph.get(a).add(new Node(b, c));
        }
 
        start = sc.nextInt();
        end = sc.nextInt();
 
        sc.close();
    }
 
    static class Node implements Comparable<Node> {
        int end;
        int weight;
 
        public Node(int end, int weight) {
            this.end = end;
            this.weight = weight;
        }
 
        @Override
        public int compareTo(Node o) {
            return weight - o.weight;
        }
    }
}