[BaekJoon] 16681 등산 (Java)

1.  문제 링크

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

2.  문제

3.  소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    static int N, M, D, E;
    static int[] height;
    static Map<Integer, List<Edge>> edges;

    static void input() {
        Reader scanner = new Reader();

        N = scanner.nextInt();
        M = scanner.nextInt();
        D = scanner.nextInt();
        E = scanner.nextInt();
        height = new int[N + 1];
        edges = new HashMap<>();
        for(int vertex = 1; vertex <= N; vertex++) {
            height[vertex] = scanner.nextInt();
            edges.put(vertex, new ArrayList<>());
        }

        for(int edge = 0; edge < M; edge++) {
            int vertex1 = scanner.nextInt(), vertex2 = scanner.nextInt(), distance = scanner.nextInt();

            edges.get(vertex1).add(new Edge(vertex2, distance));
            edges.get(vertex2).add(new Edge(vertex1, distance));
        }
    }

    static void solution() {
        // 다익스트라를 이용하여 한 지점으로부터 다른 지점으로의 최소 거리를 구한다
        // 목표 지점을 선택하여 1번 지점으로부터 목표 지점까지, 목표 지점으로부터 N번 지점까지 가는 방식이 다르기 때문에 1번 지점과 N번 지점 각각에 대해 최소 거리를 구한다
        // 1번 지점으로부터 목표 지점까지는 높이가 높은 곳으로만 이동할 수 있기 때문에 1번 지점으로부터 목표 지점까지 더 높은 높이에 있는 경우에만 이동할 수 있도록 하면서 최소 거리를 구한다
        // 목표 지점으로부터 N번 지점까지는 높이가 낮은 곳으로만 이동할 수 있으므로 반대로 N번 지점으로부터 목표 지점까지 더 높은 높이에 있는 경우에만 이동할 수 있도록 하며 최소 거리를 구한다
        // 위 방법을 이용해 1번 지점으로부터 다른 모든 지점으로의 최소 거리, N번 지점으로부터 다른 모든 지점으로의 최소 거리를 구한다
        // 이후에 1번 지점에서 이동할 수 있으면서 해당 지점에서 N번 지점으로 이동할 수 있는 곳을 찾아 그때의 가치를 구하고 그 중 최대를 찾는다
        long[] homeWeight = dijkstra(1);
        long[] universityWeight = dijkstra(N);

        long maxValue = Long.MIN_VALUE;
        for(int vertex = 1; vertex <= N; vertex++) {
            if(homeWeight[vertex] == Long.MAX_VALUE || universityWeight[vertex] == Long.MAX_VALUE) continue;
            maxValue = Math.max(maxValue, height[vertex] * E - (homeWeight[vertex] + universityWeight[vertex]) * D);
        }
        System.out.println(maxValue == Long.MIN_VALUE ? "Impossible" : maxValue);
    }

    static long[] dijkstra(int start) {
        PriorityQueue<Edge> queue = new PriorityQueue<>();
        long[] distance = new long[N + 1];
        Arrays.fill(distance, Long.MAX_VALUE);

        queue.offer(new Edge(start, 0));
        distance[start] = 0;

        while(!queue.isEmpty()) {
            Edge cur = queue.poll();
            if(distance[cur.vertex] < cur.distance) continue;

            for(Edge next : edges.get(cur.vertex)) {
                if(height[cur.vertex] >= height[next.vertex]) continue;

                int nextVertex = next.vertex;
                long nextDist = cur.distance + next.distance;
                if(distance[nextVertex] > nextDist) {
                    distance[nextVertex] = nextDist;
                    queue.offer(new Edge(nextVertex, nextDist));
                }
            }
        }

        return distance;
    }

    static class Edge implements Comparable<Edge> {
        int vertex;
        long distance;

        public Edge(int vertex, long distance) {
            this.vertex = vertex;
            this.distance = distance;
        }

        @Override
        public int compareTo(Edge o) {
            if(distance < o.distance) return -1;
            else if(distance > o.distance) return 1;
            return 0;
        }
    }

    public static void main(String[] args) {
        input();
        solution();
    }

    static class Reader {
        BufferedReader br;
        StringTokenizer st;

        public Reader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String next() {
            while(st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }

            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }
    }
}