BOJ 16681 등산

 

문제 링크 : https://www.acmicpc.net/problem/16681

16681번: 등산

 

문제에서 등산의 '가치' 를

 

 (얻은 성취감) - (소모한 체력) 으로 계산

 

라 했는데 성취감은 중간 경로에 관계없이 도달한 지점의 높이에만 의존한다. 한편, 거리당 소모 체력을 D 라 했으니

       소모한 총 체력 = D * (거리)

이므로 결국 각 지점까지의 '최단 거리' 를 구하는 문제로 환원된다.

 

각 지점까지 높이가 증가한 다음 높이가 감소한다는 식으로 생각하면 머리 아프다.

높이가 증가하는 방향으로만 진행할 수 있도록 한 다음,

한 번은 1 번 정점(집)을 출발점으로 하고 또 다른 한 번은 N 번 정점(학교)를 출발점으로 삼아서

두 번 계산하면 된다.

 

#include<bits/stdc++.h>

using namespace std;
using ll=long long;

const ll Inf=0x3f3f3f3f3f3f;

struct edge{
    int to;
    ll dst;
};

int N, M, D, E;
vector<int> Height;
vector<ll> Dst1;
vector<ll> Dst2;
vector<vector<edge>> Adj;

struct info{
    ll dst;
    int id;
    bool operator<(const info &rhs) const {
        return dst > rhs.dst;
    }
};

void find_path(int S, vector<ll> &Dst){
    Dst=vector<ll>(N+1, Inf);
    Dst[S]=0;
    priority_queue<info> pq;
    pq.push({0, S});
    
    while(!pq.empty()){
        info tInfo=pq.top();
        pq.pop();
        int cur=tInfo.id;
        
        if(Dst[cur]<tInfo.dst) continue;
        
        for(int i=0;i<Adj[cur].size();i++){
            edge te=Adj[cur][i];
            int nxt=te.to;
            if(Height[nxt]<=Height[cur]) continue;
            
            if(Dst[nxt]>tInfo.dst+te.dst){
                Dst[nxt]=tInfo.dst+te.dst;
                pq.push({Dst[nxt], nxt});
            }
        }
    }
}

int main(){
    scanf("%d%d%d%d",&N,&M,&D,&E);
    Height=vector<int>(N+1, 0);
    for(int i=1;i<=N;i++) scanf("%d", &Height[i]);
    
    Adj=vector<vector<edge>>(N+1);
    for(int i=0;i<M;i++){
        int a,b; ll c; scanf("%d%d%lld", &a,&b,&c);
        Adj[a].push_back({b, c});
        Adj[b].push_back({a, c});
    }
    
    find_path(1, Dst1);
    find_path(N, Dst2);
    
    ll res=-Inf;
    
    for(int i=1;i<=N;i++){
        if(Dst1[i]==Inf || Dst2[i]==Inf) continue;
        res=max(res, E*Height[i]-D*(Dst1[i]+Dst2[i]));
    }
    
    if(res==-Inf) printf("Impossible\n");
    else printf("%lld\n", res);
}

 

그리고 규모가 큰 거리 문제는 아예 처음부터 long long 으로 다루는 게 속편할 듯!