백준 16681 - 등산

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

힌트

집 -> 어떤 지점 방향으로는 올라가고 어떤 지점 -> 고려대학교 방향으로는 내려간다...

 

여기서 어떤 아이디어를 떠올릴 수 있겠는가?

풀이

어떤 지점 $X$를 기준으로 내려가야 되는 경로와 올라가는 경로가 다르다.

 

이를 살펴보면 $X$에서 고려대학교까지 내려가는 것은 고려대학교에서 $X$까지 올라가는 것과 같다.

 

따라서 다음과 같은 아이디어를 생각할 수 있다.

 

1. 집에서 올라가는 최단 경로 $sp_{1, x}$들을 계산한다.

2. 고려대학교에서 올라가는 최단 경로 $sp_{2, x}$들을 계산한다.

3. 어떤 지점 i에서 $sp_{1, i}$ 와 $sp_{2, i}$가 존재하면 i를 기준으로 문제 조건에 맞는 등산이 가능하고 최대 성취감을 계산할 수 있다.

 

따라서 두 최단 경로 집합을 구하기 위해 dist 배열을 두 개 만들어 시작이 1(집)과 n(고려대학교)일 때의 최단 경로를 각각 계산하고 각 정점마다 통행이 가능하면(cost가 INF 값이 아니면) 얻을 수 있는 성취감의 최댓값을 구하면 된다.

 

다익스트라 알고리즘으로 최단 경로를 구할 때 현재 지점에서 높은 지점으로만 갈 수 있다는 사실에 유의하도록 한다.

 

오버플로우를 조심하며 문제에서 요구한 답을 찾도록 하자.

 

전체 코드

#pragma GCC target("sse,sse2,sse3,ssse3,sse4,avx,avx2,fma")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")

#include "bits/stdc++.h"
#include "ext/rope"

using namespace std;
using namespace __gnu_cxx;

using pii = pair<int, int>;
using ll = long long;

#define no "Impossible"
int n, m, d, e;
vector<pii> g[100001];
int h[100001];
array<ll, 100001> dp1, dp2;

void dijkstra(int stt, array<ll, 100001> &ar)
{
    fill(ar.begin(), ar.end(), 1e18);
    using pli = pair<ll, int>;
    priority_queue<pli, vector<pli>, greater<>> pq;

    pq.push({0, stt});
    ar[stt] = 0;

    while (pq.size())
    {
        ll val;
        int node;
        tie(val, node) = pq.top();
        pq.pop();

        if (ar[node] < val) continue;

        for (auto [nnode, fee]: g[node])
        {
            ll nval = fee + val;

            if (nnode == stt || nnode == n) continue;
            if (h[nnode] <= h[node]) continue;
            if (nval >= ar[nnode]) continue;

            ar[nnode] = nval;
            pq.push({nval, nnode});
        }
    }
}

void solve()
{
    cin >> n >> m >> d >> e;

    for (int i = 1; i <= n; i++)
    {
        cin >> h[i];
    }

    for (int i = 0; i < m; i++)
    {
        int go, to, fee;
        cin >> go >> to >> fee;
        g[go].emplace_back(to, fee);
        g[to].emplace_back(go, fee);
    }

    dijkstra(1, dp1);
    dijkstra(n, dp2);

    ll ans = -1e18;

    for (int i = 2; i < n; i++)
    {
        if (dp1[i] == 1e18 || dp2[i] == 1e18) continue;
        ans = max(ans, (ll)h[i] * e - dp1[i] * d - dp2[i] * d);
    }

    if (ans == -1e18) cout << no;
    else cout << ans;
}

int main()
{
    cin.tie(nullptr);
    ios::sync_with_stdio(false);

    solve();
}

제출 기록

실수로 long long 처리를 제대로 하지 않아 몇 번 틀렸다.