[백준]등산(16681)

문제 링크 : [백준]등산(16681)

문제 설명

N개의 노드가 존재하며, 각 노드의 높아가 주어집니다.
1번 노드에서 출발하여, 2 ~ N-1 노드 중, 한 곳을 목표로 이동한 후, N 노드로 이동을 합니다.
1번 노드에서 목표 노드까지는 높이가 높아지는 방향으로만 이동 가능합니다.
목표 노드에서 N번 노드까지는 높이가 낮아지는 방향으로만 이동 가능합니다.
이때 만족도는 (E * 목표 노드의 높이) - (총 이동거리 * D)가 됩니다.
얻을 수 있는 최대 만족도를 구하세요.

입력

N(노드의 갯수, 1 <= N <= 100,000)
M(엣지의 갯수, 1 <= M <= 200,000)
D(피로도, 1 <= D <= 100)
E(성취도, 1 <= E <= 100)
H_i(노드의 높이, 1 <= H_i <= 1,000,000)
A_i B_i n_i(시작점, 도착점, 거리, 1 <= n_i <= 100,000)

8 13 4 9
1 4 7 3 10 2 15 1
1 2 3
3 4 2
5 6 6
7 8 2
2 3 4
6 7 2
3 6 1
4 8 3
5 1 6
8 3 5
2 5 4
4 6 3
5 3 8

출력

15

카테고리

#다익스트라

시간 복잡도 상한

O(N * logN) 혹은 O(M * logM)

해결 방법

1. 1에서 각 노드까지의 최단거리와 각 노드에서 N까지의 최단거리를 구합니다.
2. 최단거리를 구할 때, 오름차순과 내림차순 조건에 주의하며 구합니다.
3. 1과 N을 제외한 모든 i에 대하여, 아래 식의 값을 구합니다.
   3-1. E * H_i - (1에서 i까지의 최단거리 + i에서 N까지의 최단거리) * D
4. 3에서 구한 값중 최대값을 구합니다.
5. 그러나 1에서 각 노드까지의 최단거리는 O(M * logM)에 구할 수 있으나, 모든 노드에서 N까지의 최단거리를 구하는 것이 문제가 됩니다.
6. 양방향 그래프임을 이용하여, N에서 다른 모든 노드까지의 최단거리를 구하는 것으로 대체할 수 있습니다. 그러면 O(M * logM)에 구할 수 있습니다.
7. 단, 거꾸로 가는 것이므로, 높이가 내림차순이 아닌 오름차순으로 구해야합니다.

시간복잡도

O(M * logM)

코드

#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
#define N 100001
using namespace std;
typedef long long L;
typedef pair<L,int>P;
int n,m,d,e,i,a,b,c;
L f[N],g[N],h[N],s=-999999999999;
vector<P>v[N];
priority_queue<P,vector<P>,greater<P>>q;
void r(int s,L f[]){
    q.push({0,s});
    while(!q.empty()){
        P x=q.top();q.pop();
        if(f[x.second])continue;
        f[x.second]=x.first;
        for(P y:v[x.second])if(!f[y.second]&&h[x.second]<h[y.second])q.push({x.first+y.first,y.second});
    }
}
int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);
    cin>>n>>m>>d>>e;
    for(i=1;i<=n;i++)cin>>h[i];
    while(m--){
        cin>>a>>b>>c;
        v[a].push_back({c,b});
        v[b].push_back({c,a});
    }
    r(1,f);
    r(n,g);
    b=0;
    for(i=2;i<n;i++){
        if(f[i]&&g[i]){
            b=1;
            s=max(s,h[i]*e-(f[i]+g[i])*d);
        }
    }
    if(b)cout<<s;
    else cout<<"Impossible";
}