[백준 16681번] [Dijkstra] 등산

Approach

잘 생각해보면, 도착 높이에 대한 가치는 이미 고정되어 있는 상황이므로 해당 장소까지 방문하는데 소모된 체력을 최소한으로 만들기 위한 경로를 찾는 문제로 바뀐다.

 

추가적으로 소모된 체력은 이동 거리와 비례하는 상황이므로, 문제 상황은 최단 거리를 구하는 문제로 바뀌게 된다.

따라서 해당 지점에서 다익스트라 문제임을 쉽게 파악할 수 있다.

 

문제 조건에서 고려해야할 점은 다음과 같다.

1. 목표지점 도착 전까지는 높이가 올라가는 방향일떄만 dist 갱신이 가능하다.

2. 출발점과 목표지점, 목표지점과 고려대학교까지 도달하는 경로가 존재하지 않을 수 있다. 만약 한 경우라도 없다면 계산에서 제외시켜주어야 한다.

 

이를 위하여 다익스트라 기준점을 출발점과 고려대학교로 잡으면 된다.

(고려대학교로 잡지 않으면 2 ~ N - 1번째에서 고려대학교까지 도착하기 위한 최단거리를 구해야하므로 다익스트라를 총 N - 2번 돌려야한다.)

Code

#include <bits/stdc++.h>
#define fastio cin.tie(0)->sync_with_stdio(0)

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<int, ll> pill;
typedef pair<ll, int> plli;
int move_x[4] = {-1, 1, 0, 0};
int move_y[4] = {0, 0, -1, 1};
const ll INF = 1e13;

int main() {
    fastio;
    int n, m;
    ll d, e;
    cin >> n >> m >> d >> e;
    vector<ll> result(n);
    vector<ll> height(n);

    // Exception handling
    if(n == 2){
        cout << "Impossible\n";
        return 0;
    }

    for(int i = 0; i < n; i++){
        cin >> result[i];
        height[i] = result[i];
        result[i] *= e;
    }

    vector<pill> edge[n];
    for(int i = 0; i < m; i++){
        int a, b;
        ll c;
        cin >> a >> b >> c;
        edge[a - 1].push_back({b - 1, c});
        edge[b - 1].push_back({a - 1, c});
    }

    // Dijkstra first
    vector<ll> dist(n, INF);
    dist[0] = 0LL;
    priority_queue<plli, vector<plli>, greater<plli> > pq;
    pq.push({0LL, 0});

    while(!pq.empty()){
        ll cur_cost = pq.top().first;
        int cur = pq.top().second;
        pq.pop();
        if(dist[cur] < cur_cost) continue;
        for(auto p : edge[cur]){
            int to = p.first;
            ll cost = p.second;
            if(height[cur] < height[to] && cur_cost + cost < dist[to]){
                dist[to] = cur_cost + cost;
                pq.push({dist[to], to});
            }
        }
    }

    vector<bool> flag(n, true);
    bool total_flag = false;
    for(int i = 1; i < n - 1; i++){
        if(flag[i] && dist[i] != INF){
            result[i] -= dist[i] * d;
            total_flag = true;
        }
        else flag[i] = false;
    }
    if(!total_flag){
        cout << "Impossible\n";
        return 0;
    }

    // Dijkstra second
    fill(dist.begin(), dist.end(), INF);
    dist[n - 1] = 0;
    pq.push({0LL, n - 1});
    while(!pq.empty()){
        ll cur_cost = pq.top().first;
        int cur = pq.top().second;
        pq.pop();
        if(dist[cur] < cur_cost) continue;
        for(auto p : edge[cur]){
            int to = p.first;
            ll cost = p.second;
            if(height[cur] < height[to] && cur_cost + cost < dist[to]){
                dist[to] = cur_cost + cost;
                pq.push({dist[to], to});
            }
        }
    }

    total_flag = false;
    for(int i = 1; i < n - 1; i++){
        if(flag[i] && dist[i] != INF){
            result[i] -= dist[i] * d;
            total_flag = true;
        }
        else flag[i] = false;
    }
    if(!total_flag){
        cout << "Impossible\n";
        return 0;
    }

    ll max_num = -(1e13);
    for(int i = 1; i < n - 1; i++){
        if(flag[i]){
            max_num = max(max_num, result[i]);
        }
    }
    cout << max_num << "\n";
    return 0;
}