BOJ 16681 - 등산

www.acmicpc.net/problem/16681

16681번: 등산

 

이 문제는 다익스트라 알고리즘을 사용해야 한다.

 

이 문제의 특징은 시작지점(집) 에서 도착지점(고려대) 로 가는 최단거리를 바로 구하는게 아니라,

어떤 임의의 지점을 선정해서 그 지점을 거치고 도착지로 가야한다

 

먼저, 시작지점에서 어떤 임의의 지점까지는 항상 높이가 증가하는 방향으로 진행해야한다.

그리고 해당 지점에 도착하고 나면, 도착지점까지 가야하는데, 도착지점까지의 높이가 항상 감소하는 방향으로만 진행해야한다.

그리고 거리당 D 의 체력을 소모하며, 어떤 임의의 지점에 도착해서 목표를 달성하면, E 의 성취감을 얻게 되어있다.

등산의 가치를 문제에서는 얻은 성취감 - 소모한 체력 으로 정의하므로, 이 가치에 대한 최대값을 찾는게 문제의 목표이므로, 성취감은 크게 하고, 소모한 체력은 적게 해줘야한다.

한번에 모든 루트를 구하기 보다는, 집에서 임의의 지점까지의 거리 계산 하고 그 지점에서 도착지점까지의 거리계산 이렇게 두개로 나눠서 하는게 낫다.

 

문제에서 제시된 예제 입력 2를 보면, 가치 계산시에 음수가 나온다.

(1, 2, 3 세개의 노드가 주어지는데, 1, 3 은 시작지와 목적지로 고정되어 있어서 임의의 다른 지점은 반드시 2번이 되야 한다, 이를 기준으로 가치 계산시에 1 * E(1) - (5 + 5) * D(1) 이 되어서 무조건 음수가 나온다, 이 경우처럼 음수가 나올 수 도 있는 경우가 있으므로, 가치 계산시에 이점에 유의 해야한다)

 

 

- c++

#include <bits/stdc++.h>
 
#define INF LLONG_MAX 
#define MAX 100001
 
using namespace std;
 
typedef long long ll;
 
int N, M, D, E;
vector<int> height; // 높이 저장을 위한 벡터 
vector<pair<int, int>> adj[MAX]; // 연결지점, 거리 
 
ll dijkstra() {
    // 집에서 특정 지점 까지의 거리
    vector<ll> dist1(N + 1, INF);
    priority_queue<pair<ll, int>> pq; // 거리, 노드 번호 
    pq.push({0, 1});
    
    while(!pq.empty()) {
        ll distance = -pq.top().first;
        int cur = pq.top().second;
        pq.pop();
        
        if (distance > dist1[cur]) continue; // 최단거리가 아닐때
        
        for (int i = 0; i < adj[cur].size(); ++i) {
            ll next_dist = adj[cur][i].second + distance;
            int next_node = adj[cur][i].first;
            
            if (dist1[next_node] > next_dist && height[next_node] > height[cur]) {
                // 집에서 어떤 지점까지는 항상 높이가 증가하는 방향으로 처리되야하고, 최단거리를 갱신해야함.
                dist1[next_node] = next_dist;
                pq.push({-next_dist, next_node}); 
            }
        } 
    } 
    
    // 목적지인 고려대에서 어떤 지점까지의 거리 구하기
    vector<ll> dist2(N + 1, INF);
    pq.push({0, N});
    
    while(!pq.empty()) {
        ll distance = -pq.top().first;
        int cur = pq.top().second;
        pq.pop();
        
        if (distance > dist2[cur]) continue;
        
        for (int i = 0; i < adj[cur].size(); ++i) {
            ll next_dist = adj[cur][i].second + distance;
            int next_node = adj[cur][i].first;
            
            if (dist2[next_node] > next_dist && height[next_node] > height[cur]) {
                dist2[next_node] = next_dist;
                pq.push({-next_dist, next_node});
            }
        }
    } 
    
    ll value = -INF;
    for (int i = 2; i < N; ++i) {
        if (dist1[i] == INF || dist2[i] == INF) continue; // 경로가 없는 경우 패스함.
        
        ll tmp = height[i] * E - (dist1[i] + dist2[i]) * D; // 높이 * 성취감 - 거리당 소모된 체력 
        value = max(value, tmp);
    }
    
    return value;
}
 
int main() {
    cin.tie(0); ios_base::sync_with_stdio(0);
    
    cin >> N >> M >> D >> E;
    
    height.resize(N + 1);
    for (int i = 1; i <= N; ++i) {
        cin >> height[i];
    }
    
    for (int i = 0; i < M; ++i) {
        int a, b, n;
        cin >> a >> b >> n;
        adj[a].push_back({b, n}); // 양방향 경로라 했으므로 둘다 이어줌 
        adj[b].push_back({a, n});
    }
    
    ll temp = dijkstra();
    if (temp == -INF) cout << "Impossible";
    else cout << temp;
    
    return 0;
}