[백준 16681] 등산 C++

16681번: 등산

다익스트라

---

 

시작점은 항상 1이고 도착점은 항상 N이다.

 

시작점에서 도착점으로 가면서 높이가 점점 높아지는 최단거리 다익스트라를 수행한다.

도착점에서 시작점으로 가면서 높이가 점점 높아지는 최단거리 다익스트라를 수행한다.

임의의 가운데 정점을 잡고 해당 정점이 시작점과 도착점 모두와 연결되어있다면

위 2개의 다익스트라를 통해서

시작점과 연결된 최단거리는 자연스럽게 높이가 증가하는 최단거리가 구해지고, 

임의의 정점에서 도착점으로 가는 최단거리는 높이가 감소하는(반대로 도착점에서 정점을 보면 높이가 증가하는) 최단거리를 구할 수 있다.

 

따라서 모든 지점을 한 번씩 가운데 경로로 지정해 주었을 때 (얻은 성취감) - (소모한 체력)의 최솟값을 구한다. O(N)

 

 

주의할 점.

거리와 관련된 모든 변수는 long long을 사용한다.

거리는 최대 100,000, 경로의 최대 개수 100,000 이므로 둘을 곱하면 10 ^ 12.

음수도 가능하므로 최솟값도 매우 작게 설정.

 

 

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <cstring>
#define fasti ios_base::sync_with_stdio(false); cin.tie(0);
#define fastio ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define INF 1e13+7
 
typedef long long ll;
#define pii pair<ll, int>
// typedef pair<int, int> pii;
 
using namespace std;
 
int N, M, D, E;
long long Height[100001];
vector<pii > Route[100001];
ll dist[100001][2];
long long Value;
 
void input(){
    cin >> N >> M >> D >> E;
    for(int i = 1; i <= N; i++){
        cin >> Height[i];
    }
    int a, b, c;
    for(int i = 0; i < M; i++){
        cin >> a >> b >> c;
        Route[a].push_back({c, b});
        Route[b].push_back({c, a});
    }
    for(int i = 0; i <= N; i++){
        dist[i][0] = INF;
        dist[i][1] = INF;
    }
}
 
void Dijkstra(int st, int k){
    priority_queue<pii, vector<pii >, greater<pii > > pque;
    pque.push({0, st});
    dist[st][k] = 0;
    
    while(!pque.empty()){
        int now_idx = pque.top().second;
        ll min_cost = pque.top().first;
        pque.pop();
        
        if(min_cost > dist[now_idx][k]){
            continue;
        }
        
        for(int i = 0; i < Route[now_idx].size(); i++){
            int next = Route[now_idx][i].second;
            ll next_cost = Route[now_idx][i].first + min_cost;
            if(dist[next][k] > next_cost && Height[next] > Height[now_idx]){
                dist[next][k] = next_cost;
                pque.push({next_cost, next});
            }
        }
    }
}
 
void drive_answer(){
    ll maxi = -INF * 100000;
    for(int i = 1; i <= N; i++){
        maxi = max(maxi, Height[i]*E - D * (dist[i][0] + dist[i][1]));
    }
    
    if(maxi == -INF * 100000) cout << "Impossible" << '\n';
    else cout << maxi << '\n';
}
 
void solve(){
    // 시작점에서 다익스트라
    Dijkstra(1, 0);
    // 도착점에서 다익스트라
    Dijkstra(N, 1);
    
    drive_answer();
}
 
int main(){
    input();
    solve();
    
    return 0;
}