[파이썬, 자바] 백준 5972 : 택배 배송 (골드5)

[파이썬, 자바] 백준 5972 : 택배 배송 (골드5)

• https://www.acmicpc.net/problem/5972

---

풀이

방향성 생각

• 그냥 기본 다익

 

---

파이썬

import heapq as hq
import sys

input = lambda : sys.stdin.readline().rstrip()
INF = sys.maxsize

N,M = map(int,input().split())

G = [[] for _ in range(N+1)]
for _ in range(M):
    a,b,cost = map(int,input().split())
    G[a].append((b,cost))
    G[b].append((a,cost))

V = [INF]*(N+1)
V[1] = 0

heap = [(0,1)]
while heap:

    t,x = hq.heappop(heap)
    for nx,cost in G[x]:

        nt = t+cost
        if nt < V[nx]:
            hq.heappush(heap,(nt,nx))
            V[nx] = nt
print(V[N])

---

자바

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

public class Main {

import java.io.*;
import java.util.*;
public class Main {

    public static void main(String args[]) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        ArrayList<ArrayList<int[]>> G = new ArrayList<>();
        for (int i=0; i<=N; i++) {
            G.add(new ArrayList<>());
        }

        for (int i=0; i<M; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int cost = Integer.parseInt(st.nextToken());
            G.get(a).add(new int[]{cost, b});
            G.get(b).add(new int[]{cost, a});
        }

        int[] V = new int[N+1];
        Arrays.fill(V, Integer.MAX_VALUE);
        V[1] = 0;

        PriorityQueue<int[]> heap = new PriorityQueue<>(Comparator.comparingInt(a -> a[0]));
        heap.add(new int[]{0, 1});

        while (!heap.isEmpty()) {
            int[] info = heap.poll();
            int t = info[0], x = info[1];

            for (int[] ninfo : G.get(x)) {
                int nt = t + ninfo[0];
                int nx = ninfo[1];

                if (nt < V[nx]) {
                    V[nx] = nt;
                    heap.add(new int[]{nt,nx});
                }
            }
        }
        System.out.println(V[N]);
    }
}

 

• BufferedReader + StringTokenizer로 한 줄 읽고 next Token 사용하기
• 인접리스트 구현할떄는 ArrayList 중첩하기.
• 접근에는 get. 값 추가는 add
• Array 값 초기화는 Arrays.fill(배열, 값)
• PQ에는 Comparator.comparingInt 사용하기

---

코멘트

• .