230902 - [Java-Python] 최단거리

[robert-min]

1916

[robert-min]

BOJ.1916 최소비용 구하기 링크

• 문제풀이
  • 목적지까지 최소 비용을 구하는 문제이고, 구간마다 걸리는 시간이 있기 때문에 다익스트라 알고리즘으로 풀어야 함
  • 다익스트라 알고리즘의 경우 특정 노드로 가는 최소 시간만을 탐색하기 때문에 최소 힘(heapq)를 사용
  • heapq에는 (해당노드 까지 누적 시간, 해당 노드)값을 사용

python

import sys
input = sys.stdin.readline

N = int(input())
M = int(input())

from collections import defaultdict
graph = defaultdict(list)
for _ in range(M):
    u, v, w = map(int, input().split())
    graph[u].append((v, w))

start, end = map(int, input().split())

# dikstra -> heapq
import heapq

Q = [(0, start)]

dist = defaultdict(list)
while Q:
    time, now = heapq.heappop(Q)

    if now not in dist:
        dist[now] = time
        for v, w in graph[now]:
            alt = time + w
            heapq.heappush(Q, (alt, v))

print(dist[end])

java

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

class Node implements Comparable<Node> {
    int nodeNum;
    int weight;

    public Node(int nodeNum, int weight) {
        this.nodeNum = nodeNum;
        this.weight = weight;
    }

    @Override
    public int compareTo(Node o) {
        return weight - o.weight;
    }
}

public class Main {

    static int N, M, A, B;
    static List<ArrayList<Node>> list;
    static int[] dist;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        M = Integer.parseInt(br.readLine());

        list = new ArrayList<>();
        for (int i = 0; i <= N; i++) {
            list.add(new ArrayList<>());
        }
        for (int i = 1; i <= M; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            int w = Integer.parseInt(st.nextToken());

            list.get(u).add(new Node(v, w));
        }

        StringTokenizer st = new StringTokenizer(br.readLine());
        A = Integer.parseInt(st.nextToken());
        B = Integer.parseInt(st.nextToken());

        solution();
    }

    static void solution() {
        dist = new int[N+1];
        dikstra(A, B);
    }

    static void dikstra(int start, int dest) {
        PriorityQueue<Node> Q = new PriorityQueue<Node>();
        boolean[] visited = new boolean[N+1];

        dist[start] = 0;
        Q.offer(new Node(start, 0));
        while (!Q.isEmpty()) {
            Node node = Q.poll();
            int now = node.nodeNum;
            int time = node.weight;

            if (!visited[now]) {
                dist[now] = time;
                visited[now] = true;
                for (Node next : list.get(now)) {
                    Q.offer(new Node(next.nodeNum, next.weight + time));
                }
            }

        }
        System.out.println(dist[dest]);

    }

}