[백준] 16681번 등산

16681 등산

문제

---

주환이는 요즘 등산에 빠졌다. 주환이는 등산을 위해 지도를 가지고 있는데, 그 지도에는 각 지점의 높이와 갈 수 있는 다른 지점까지의 거리가 표시되어 있다.주환이는 아침에 집에서 출발하여 등산을 갔다가, 오후 수업을 듣기 위해 고려대학교로 돌아와야 한다.

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

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

입력

---

첫 번째 줄에 지도에 표시된 지점의 개수, 지점을 잇는 경로의 개수, 주환이의 거리 비례 체력 소모량, 높이 비례 성취감 획득량을 나타내는 정수 N, M, D, E가 공백을 사이에 두고 주어진다. (2 ≤ N ≤ 100,000, 1 ≤ M ≤ 200,000, 1 ≤ D ≤ 100, 1 ≤  E ≤ 100)

두 번째 줄에 N개의 정수 h1, ...  ,hN이 공백으로 구분되어 주어진다. hi는 i 번째 지점의 높이를 의미한다. (1 ≤ hi ≤ 1,000,000, 1 ≤ i ≤ N)

세 번째 줄부터 M개의 줄에 걸쳐 세 정수 a, b, n이 공백으로 구분되어 주어진다. 이는 a번 지점과 b번 지점을 잇는 거리 n의 양방향 경로가 있음을 의미한다. (1 ≤ a, b ≤ N, 1 ≤ n ≤ 100,000)

어떤 지점에서 다른 지점으로 가는 경로가 여러 개 있을 수도 있으며 (등산로는 여러 개가 있을 수 있다), 한 지점에서 출발해 그 지점으로 돌아가는 경로가 있을 수도 있다 (쉼터에서 몇 바퀴 돌며 쉴 수도 있다).

주환이의 집은 1번 지점에 위치하고, 고려대학교는 N번 지점에 위치하며 주환이의 집과 고려대학교의 높이는 1임이 보장된다.

출력

---

첫번째 줄에 주환이가 얻을 수 있는 가치의 최댓값을 출력한다. 만약 조건을 만족하는 등산 경로를 선택할 수 없다면, "Impossible"을 쌍따옴표를 제외하고 출력한다. 답이 음수일 수 있음에 유의하여라.

---

풀이)

가치가 최대여야하니깐 소모한 체력인 최소여야하고, 얻은 성취감은 최대여야한다.

(가치↑ = 성취감↑ - 체력↓)

체력이 최소이려면 거리가 최소여야하므로 지점 사이의 최소 거리를 구할 수 있는 다익스트라를 사용한다.

(체력↓ = 거리↓ * D)

주환이가 정한 목표까지는 높이가 계속 올라가야하고, 목표에서 고려대학교까지는 높이가 계속 내려가야하니깐

동시에 거리와 높이를 고려하기가 복잡했다.

그래서 거리를 2개로 나눠서 구했다.

1. 집에서 목표까지                                                             2. 고려대학교에서 목표까지

*주의할점*

가치는 음수가 나올 수 있으므로 초기값을 가장 작은 값으로 설정해주어야한다.

경로가 없어서 특정 지점까지 못가는 경우도 있을 수 있다.

코드)

#include <stdio.h>
#include <queue>
#include <vector>
#include <algorithm>
#include <climits>
using namespace std;
 
#define INF LLONG_MAX
typedef long long ll;
 
int n, m, d, e;
vector <int> height; //지점들의 높이를 저장
vector <pair<int,int>> adj[100001]; //각 지점들마다 <연결되있는 지점, 지점을 잇는 거리> 저장
 
ll Dijkstra() {
    //1. 집 -> 지점
    vector <ll> dist1(n + 1, INF);
    priority_queue <pair<ll, int>> qu;
    qu.push(make_pair(0, 1));
    while (!qu.empty())
    {
        ll d = -qu.top().first;
        int here = qu.top().second;
        qu.pop();
 
        if (d > dist1[here]) continue;
 
        for (int i = 0; i < adj[here].size(); i++) {
            ll nextd = adj[here][i].second + d;
            int next = adj[here][i].first;
            //항상 높이가 증가하는 방향으로만 이동
            if (dist1[next] > nextd && height[next] > height[here]) {
                dist1[next] = nextd;
                qu.push({ -nextd,next });
            }
        }
    }
    //2. 고려대학교 -> 지점
    vector <ll> dist2(n + 1, INF);
    qu.push({ 0,n });
    while (!qu.empty())
    {
        ll d = -qu.top().first;
        int here = qu.top().second;
        qu.pop();
 
        if (d > dist2[here]) continue;
 
        for (int i = 0; i < adj[here].size(); i++) {
            ll nextd = adj[here][i].second + d;
            int next = adj[here][i].first;
            //지점에서 고려대학교까지는 항상 높이가 감소해야하니깐
            //고려대학교에서 지점까지는 항상 높이가 증가하는 방향으로만 이동
            if (dist2[next] > nextd && height[next] > height[here]) {
                dist2[next] = nextd;
                qu.push({ -nextd,next });
            }
        }
    }
 
    //가치 계산, 음수일수도 있다
    ll value = -INF;
    for (int i = 2; i < n; i++) {
        //만약 집에서 i지점까지, 혹은 i지점에서 고려대학교까지 가는 경로가 없다면 pass
        if (dist1[i] == INF || dist2[i] == INF) continue;
 
        ll temp = height[i]*e - (dist1[i] + dist2[i])*d;
        value = max(value, temp);
    }
 
    return value;
}
 
int main() {
    scanf("%d %d %d %d", &n, &m, &d, &e);
    height.resize(n + 1); //지점의 번호를 1부터 시작하기 위해 n+1로 사이즈를 정해줌
    for (int i = 1; i <= n; i++) {
        scanf("%d", &height[i]);
    }
    for (int i = 0; i < m; i++) {
        int a, b, c;
        scanf("%d %d %d", &a, &b, &c);
        adj[a].push_back({ b,c });
        adj[b].push_back({ a,c }); //양방향이므로
    }
 
    ll tmp = Dijkstra();
    if (tmp == -INF) {
        printf("Impossible");
    }
    else {
        printf("%lld", tmp);
    }
 
    return 0;
}

결과)