BJ G5 5972 택배배송

BJ G5 5972 택배배송

 

 

문제링크

http://www.acmicpc.net/problem/5972

5972번: 택배 배송

* 일단 문제를 정독 하고 1시간 이상 반드시 고민이 필요합니다.

 

동영상 설명

1시간 이상 고민 했지만 아이디어가 떠오르지 않는다면 동영상에서 약간의 힌트를 얻어봅시다.

youtu.be/D0aMh9orWYo

 

 

소스 보기

동영상 설명을 보고도 전혀 구현이 안된다면 이건 연습 부족입니다.
소스를 보고 작성해 본 후 스스로 백지 상태에서 3번 작성해 볼 의지가 있다면 소스를 살짝 보세요.

package bj.gold.l5;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StringReader;
import java.util.ArrayList;
import java.util.List;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

/**
 * @author itsmeyjc
 * @since 2020. 5. 23.
 * @see https://www.acmicpc.net/problem/5972
 * @mem 39676
 * @time 392
 * @caution #dijkstra,
 * 두 점간 최단 거리 문제
 * 정점의 개수가 50000개로 매우 큼 - 그래프 구성시 인접 행렬은 25억개. ㅜㅜ - 인접 리스트 필요
 */

public class BJ_G5_5972_택배배송 {

    static BufferedReader input = new BufferedReader(new InputStreamReader(System.in));

    static int N; // N (1 <= N <= 50,000) 개의 헛간 - 정점(인접 행렬로 그래프 구성시 너무 큼: 5만*5만 = 25억 - 인접 리스트)
    static int M; // M (1 <= M <= 50,000) 개의 양방향 길 - 무향 그래프

    static List<Edge>[] graph;

    static int INF = 987654321;
    // 구해야 할 정답
    static int Min;

    @SuppressWarnings("unchecked")
    public static void main(String[] args) throws IOException {
        input = new BufferedReader(new StringReader(src));

        // 입력 및 그래프 구성
        StringTokenizer tokens = new StringTokenizer(input.readLine(), " ");

        N = Integer.parseInt(tokens.nextToken()) + 1;// 1번 부터 시작한다.
        M = Integer.parseInt(tokens.nextToken());

        // 인접 리스트 형태로 그래프 구성
        graph = new List[N];
        for (int i = 1; i < graph.length; i++) {
            graph[i] = new ArrayList<>();
        }

        for (int m = 0; m < M; m++) {
            tokens = new StringTokenizer(input.readLine(), " ");
            int from = Integer.parseInt(tokens.nextToken());
            int to = Integer.parseInt(tokens.nextToken());
            int cow = Integer.parseInt(tokens.nextToken());
            // 양방향 그래프
            graph[from].add(new Edge(to, cow, 0));
            graph[to].add(new Edge(from, cow, 0));
        }
        /*        for (int[] row : graph) {
            System.out.println(Arrays.toString(row));
        }*/
        // 1--> 6으로 가는 최소 비용(특정 점 간의 최소 비용: dijkstra)
        Min = Integer.MAX_VALUE;
        dijkstra();
        System.out.println(Min == Integer.MAX_VALUE ? 0 : Min);
    }

    static void dijkstra() {
        PriorityQueue<Edge> pq = new PriorityQueue<>();
        // 일단 무한대로 출발지에서의 누적 비용을 초기화해서 정점들을 관리할 배열
        Edge[] dist = new Edge[N];
        for (int i = 1; i < dist.length; i++) {
            Edge v = new Edge(i, 0, INF);
            if (i == 1) {
                v.cumCost = 0; // 출발점
                pq.offer(v);
            }
            dist[i] = v;
        }

        while (!pq.isEmpty()) {
            Edge front = pq.poll();

            // 자식 탐색
            List<Edge> list = graph[front.no];
            for (int i = 0; i < list.size(); i++) {
                Edge next = list.get(i);
                // 기존 누적 비용이 front를 거쳐서 온 비용보다 크다면 갱신 필요
                if (dist[next.no].cumCost > front.cumCost + next.cost) {
                    dist[next.no].cumCost = front.cumCost + next.cost;
                    // 다음 탐색 후보로 등록
                    pq.offer(dist[next.no]);
                }
            }
        }
        // System.out.println("정점: " + vertexes[N - 1]);
        Min = dist[N - 1].cumCost;
    }

    static class Edge implements Comparable<Edge> {
        int no;
        // 해당 간선의 비용으로 graph에서 사용
        int cost;
        // 출발점에서 부터의 누적 비용으로 dist에서 사용
        int cumCost;

        public Edge(int no, int cost, int cumCost) {
            this.no = no;
            this.cost = cost;
            this.cumCost = cumCost;
        }

        public int compareTo(Edge o) {
            return Integer.compare(this.cumCost, o.cumCost);
        }
    }

    private static String src = "6 8\r\n" +
                                "4 5 3\r\n" +
                                "2 4 0\r\n" +
                                "4 1 4\r\n" +
                                "2 1 1\r\n" +
                                "5 6 1\r\n" +
                                "3 6 2\r\n" +
                                "3 2 6\r\n" +
                                "3 4 4";
}