[백준] 16681번 등산

[적용한 알고리즘]

다익스트라

 

[아이디어]

 

목표지로 갈 때, 어차피 추가되는 성취감은 각 노드를 어떤 식으로 방문했든 h * E 로 일정하다.

그러므로, 가치가 최대가 되려면, 잃는 체력을 최소로 만들면 된다.

 

[생각의 흐름 / 절차] 

문제의 주인공이 하는 짓을 2개의 파트로 나눌 수 있다.

1. 목표지로 간다.

2. 고려대(부럽..)으로 간다. 

 

따라서, 2개의 절차로 나누어서 생각해볼 수 있다.

1. 1번 노드에서 X (2<= X <= N - 1) 번 노드로 가는 최소거리를 저장하는 dist 배열

2. N번 노드에서 X (2<= X <= N - 1)번 노드로 가는 최소거리를 저장하는 dist2 배열

을 다익스트라로 구해준 뒤, E * height[X] - (dist[X] + dist2[X]) * D 의 최댓값을 찾아주면 된다.

 

[교훈]

문항이 요구하는 조건을 정확하게 구현하는게 쉽지는 않았다. 

문제를 천천히 읽어보면서 다익스트라라는 감을 잡아야겠다.

그리고, 로직은 맞는거 같은데 계속 틀렸길래 자료형을 다 long long 으로 뜯어 고치고, 별 짓을 다했다.

코드가 복잡해 가독성이 많이 떨어지니 다시 깔끔하게 코드를 쓰고 업데이트를 해야겠다. (업데이트 완료)

 

<코드>

#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>
#define INF 1000000000000
const int MAX_N = 100001;
using namespace std;
typedef pair<int, long long> P;
typedef long long int lld;
int N, M, D, E; //D: 체력 소모량, E: 성취감
int height[MAX_N];
vector<P> adj[MAX_N];

void dijkstra(int start_node, lld dist[]){
    priority_queue<P, vector<P>, greater<P>> PQ;
    bool visited[MAX_N] = { 0 };
    fill(dist, dist + N + 1, INF);
    dist[start_node] = 0;
    PQ.push(P(0, start_node));

    while (!PQ.empty()){
        int cur;
        do {
            cur = PQ.top().second;
            PQ.pop();
        } while (!PQ.empty() && visited[cur]);

        if (visited[cur]) break;
        visited[cur] = true;

        for (auto &p : adj[cur]){
            int nxt_node = p.first;
            int nxt_cost = p.second;

            if (height[nxt_node] > height[cur]){
                if (dist[nxt_node] > dist[cur] + nxt_cost){
                    dist[nxt_node] = dist[cur] + nxt_cost;
                    PQ.push(P(dist[nxt_node], nxt_node));
                }
            }
        }
    }
}
int main(){
    scanf("%d %d %d %d", &N, &M, &D, &E);
    for (int i = 1; i <= N; i++){
        scanf("%d", &height[i]);
    }

    for (int i = 1; i <= M; i++){
        int from, to, cost;
        scanf("%d %d %d", &from, &to, &cost);
        adj[from].push_back(P(to, cost));
        adj[to].push_back(P(from, cost));
    }

    lld dist1[MAX_N];
    lld dist2[MAX_N];

    dijkstra(1, dist1);
    dijkstra(N, dist2);

    lld ans = -INF;

    for (int i = 2; i <= N - 1; i++){
        if (dist1[i] == INF || dist2[i] == INF) continue;
        lld res = height[i] * E - (dist1[i] + dist2[i]) * D;
        ans = max(ans, res);
    }

    if (ans == -INF) printf("Impossible\n");
    else printf("%lld", ans);

    return 0;
}