백준 11779 - 최소비용 구하기 2

문제

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

11779번: 최소비용 구하기 2

 

 

 

풀이

 

다익스트라 알고리즘을 이용하여 최소비용을 구한다. 노드 간의 최단거리가 갱신될 때 부모 노드를 갱신해줘서 도착점과 시작점 사이의 길을 알 수 있게 만든다.

 

 

 

코드

 

python

import heapq
n = int(input())
m = int(input())
 
graph = [[] for _ in range(n + 1)]
INF = int(1e9)
dist = [INF] * (n + 1)
parent = [i for i in range(n + 1)]
 
for _ in range(m):
    a, b, c = map(int, input().split())
    graph[a].append((b, c))
 
start, end = map(int, input().split())
 
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]))
                parent[i[0]] = now
        
dijkstra(start)
print(dist[end])
st = []
cnt = 1
i = end
st.append(i)
while i != start:
    i = parent[i]
    cnt += 1
    st.append(i)
 
print(cnt)
while st:
    print(st.pop(), end=' ')

 

java

import java.io.*;
import java.util.*;
 
public class Main {
 
    static int n, m;
    static List<List<Node>> graph;
    static int start, end;
    static int[] dist;
    static int[] parent;
 
    public static void main(String[] args) throws IOException {
        input();
        dijkstra(start);
        solve();
    }
 
    private static void solve() throws IOException {
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        bw.write(dist[end] + "\n");
        Stack<Integer> st = new Stack<>();
        for (int i=end; i!=start; i=parent[i]) {
            st.push(i);
        }
        st.push(start);
        bw.write(st.size()+"\n");
        while (!st.isEmpty()) {
            bw.write(st.pop() + " ");
        }
        bw.close();
    }
 
    private static void dijkstra(int start) {
        PriorityQueue<Node> pq = new PriorityQueue<>();
        pq.add(new Node(start, 0));
        dist[start] = 0;
 
        while (!pq.isEmpty()) {
            Node cur = pq.poll();
            int distance = cur.weight;
            int now = cur.end;
 
            if (distance > dist[now])
                continue;
 
            for (Node nextNode : graph.get(now)) {
                int cost = nextNode.weight + distance;
                int next = nextNode.end;
                if (dist[next] > cost) {
                    dist[next] = cost;
                    pq.add(new Node(next, cost));
                    parent[next] = now;
                }
            }
        }
    }
 
    private static void input() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        m = Integer.parseInt(br.readLine());
 
        parent = new int[n + 1];
        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;
            String[] strs = br.readLine().split(" ");
            a = Integer.parseInt(strs[0]);
            b = Integer.parseInt(strs[1]);
            c = Integer.parseInt(strs[2]);
 
            graph.get(a).add(new Node(b, c));
        }
        String[] strs = br.readLine().split(" ");
        start = Integer.parseInt(strs[0]);
        end = Integer.parseInt(strs[1]);
        br.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;
        }
    }
}