백준 16681 (등산) - java

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

 

문제

주환이는 요즘 등산에 빠졌다. 주환이는 등산을 위해 지도를 가지고 있는데, 그 지도에는 각 지점의 높이와 갈 수 있는 다른 지점까지의 거리가 표시되어 있다.

주환이는 아침에 집에서 출발하여 등산을 갔다가, 오후 수업을 듣기 위해 고려대학교로 돌아와야 한다.

1. 주환이는 지도의 임의의 지점을 골라, 그 지점을 목표로 정한다. 집 또는 고려대학교는 목표로 선택할 수 없다.
2. 주환이가 집에서 정한 목표에 도달할 때 까지는 항상 높이가 증가하는 방향으로만 이동해야 한다.
3. 주환이가 정한 목표에 도달한 후, 고려대학교로 갈 때에는 항상 높이가 감소하는 방향으로만 이동해야 한다.
4. 주환이는 거리 1을 움직일 때 마다 D 의 체력이 소모된다.
5. 주환이는 정한 목표에 도달하면 높이 1당 E 의 성취감을 얻는다. 즉 높이가 h인 목표에 도달하면 hE의 성취감을 얻는다.

주환이는 이 등산의 가치를 (얻은 성취감) - (소모한 체력) 으로 계산하기로 하였다. 주환이를 위해 가치가 가장 높은 등산 경로를 선택해주자.

 

유형 : 다익스트라

 

접근 방식

• 이동할 때 드는 체력을 기준으로 다익스트라를 수행하면 된다.
• 목표 -> 고려대학교(n번째 지점)의 이동을 고려대학교(n번째 지점) -> 목표로 생각하고 다익스트라를 한번 더 수행한다.
  • 반대로 수행하는 경우이므로 높이가 증가하는 이동을 적용하면 된다.
  • 즉 하나의 메서드를 2번 수행한다 생각하면 더한다.
• 주어진 조건식 (얻은 성취감) - (소모한 체력)을 만족하는 최댓값을 구한다.
• Long 주의 !

 

전체 코드

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

public class Main {

    static int n,m,d,e;
    static int[] height;

    static ArrayList<Node>[] graph;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine()," ");

        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        d = Integer.parseInt(st.nextToken());
        e = Integer.parseInt(st.nextToken());

        height = new int[n+1];
        graph = new ArrayList[n+1];
        st = new StringTokenizer(br.readLine()," ");
        for(int i = 1 ; i <= n ; i++) {
            height[i] = Integer.parseInt(st.nextToken());

            graph[i] = new ArrayList<>();
        }

        for(int i = 1 ; i <= m ; i++) {
            st = new StringTokenizer(br.readLine()," ");

            int v1 = Integer.parseInt(st.nextToken());
            int v2 = Integer.parseInt(st.nextToken());
            long c = Long.parseLong(st.nextToken());

            graph[v1].add(new Node(v2,c));
            graph[v2].add(new Node(v1,c));
        }

        long[] dis1 = search(1);
        long[] dis2 = search(n);

        long result = Long.MIN_VALUE;

        for(int i = 2 ; i <= n - 1 ; i++) {
            if(dis1[i] != Long.MAX_VALUE && dis2[i] != Long.MAX_VALUE) {
                result = Math.max(result,(height[i] * e) - (dis1[i] + dis2[i]));
            }
        }

        if(result == Long.MIN_VALUE) {
            System.out.println("Impossible");
        }else {
            System.out.println(result);
        }


        br.close();
    }

    static long[] search(int start) {
        PriorityQueue<Node> pq = new PriorityQueue<>(
                (x,y) -> Long.compare(x.c,y.c)
        );

        long[] dis = new long[n+1];
        for(int i = 1 ; i <= n ; i++) {
            dis[i] = Long.MAX_VALUE;
        }

        dis[start] = 0;
        pq.add(new Node(start,0));

        while(!pq.isEmpty()) {
            Node cur = pq.poll();

            if(dis[cur.v] < cur.c)
                continue;

            for(Node next : graph[cur.v]) {
                if(height[next.v] <= height[cur.v])
                    continue;

                if(dis[next.v] <= cur.c + (next.c * d)) {
                    continue;
                }

                dis[next.v] = cur.c + (next.c * d);
                pq.add(new Node(next.v,dis[next.v]));
            }
        }

        return dis;
    }

    static class Node {
        int v;
        long c;

        Node(int v,long c) {
            this.v = v;
            this.c = c;
        }
    }
}