16681번-등산

문제

https://www.acmicpc.net/problem/16681

16681번: 등산

---

접근방법

1) 접근 사고

 

2) 시간 복잡도

 

3) 배운 점

 

4) PS

---

정답 코드

#include<bits/stdc++.h>
#define fastio ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define pii pair<int,int>
#define mp(X,Y) make_pair(X,Y)
#define mt(X,Y) make_tuple(X,Y)
#define mtt(X,Y,Z) make_tuple(X,Y,Z)
#define ll long long
#define sz(v) (int)(v).size()
 
using namespace std;
const int MAX = 100001;
const ll INF = 2300987654321;
ll height[MAX];
ll point_dist[MAX];
ll univ_dist[MAX];
vector<pair<int,int>> edge[MAX];
//n: n번째 줄에 표시된 지점의 개수
//m: 지점을 이슨 경로의 개수
//d: 주환이의 거리 비례 체력 소모량
//e: 높이 비례 성취감 획득량
int n, m, d, e;
int main(void)
{
    fastio;
    cin >> n >> m >> d >> e;
    for(int i = 1; i <= n; i++)
    {
        cin >> height[i];
        point_dist[i] = univ_dist[i] = INF;
    }
 
    for(int i = 1; i <= m; i++)
    {
        int a, b, n;
        cin >> a >> b >> n;
        edge[a].push_back({n,b});
        edge[b].push_back({n,a});
    }
 
    auto dijkstra = [&](int start, ll visited[]){
        priority_queue<pair<ll,ll>, vector<pair<ll,ll>>, greater<pair<ll,ll>>> pq;
        pq.push({0, start});
        visited[start] = 0;
 
        while(!pq.empty())
        {
            ll cost = pq.top().first;
            int cur = pq.top().second;
            pq.pop();
 
            if(cost > visited[cur])
                continue;
 
            for(auto idx : edge[cur])
            {
                int neighbor = idx.second;
                ll neighborCost = idx.first + cost;
 
                //주환이가 집에 정한 목표에 도달할 때까지는 항상 높이가 증가하는 방향으로 가야한다.
                if (height[cur] >= height[neighbor])
                    continue;
 
                if(visited[neighbor] > neighborCost)
                {
                    visited[neighbor] = neighborCost;
                    pq.push({neighborCost, neighbor});
                }
            }
        }
            };
 
    //출발 지점 -> 등산 지점 <- 대학교의 합계를 구하는 과정
    //출발지에서 각 등산 지점까지의 최단거리
    dijkstra(1, point_dist);
    //도착지에서 각 등산 지점까지의 최단거리
    dijkstra(n, univ_dist);
 
    ll ans = -INF;
    for(int i = 2; i <n; i++)
    {
        //등산 경로가 없는 경우 예외처리
        if(point_dist[i] == INF || univ_dist[i] == INF)
            continue;
        //높이 * 높이 비례 성취감 - 주환이의 거리 비례 체력소모량 * (각 등산 지점까의 거리 합계 (위에서 다이젝스트라로 구한 거리))
        ll cost = height[i] * e - d * (point_dist[i] + univ_dist[i]);
        ans = max(ans, cost);
    }
 
    if(ans == -INF)
    {
        cout << "Impossible\n";
    }
    else
        cout << ans <<"\n";
}