BOJ 16681 - 등산 링크
(2023.07.14 기준 G2)

문제

N개의 지점, 지점을 잇는 경로 M개, 거리 1당 체략 소모량 D, 높이 1당 성취감 E가 주어진다.

집(1번)과 고려대(N번)을 제외한 임의의 지점을 골라 집에서 출발하여 지점에 도착 후, 고려대로 돌아간다. 이 때, 지점까지는 높이가 증가하는 방향, 고려대로 돌아올 땐, 높이가 감소하는 방향으로만 이동할 수 있다.

등산의 가치는 (고른 지점의 높이에 따른 성취감) - (총 거리에 따른 체력 소모)으로 계산할 때, 가치가 가장 높은 등산 경로의 가치 출력

알고리즘

다익스트라

풀이

올라갈 땐, 높이가 항상 증가. 내려갈 땐 높이가 항상 감소여야 한다.
그렇다고 모든 지점마다 고려대로 돌아가는 거리 및 가치 계산을 하면 안된다.

출발점은 집, 도착점은 고려대로 고정되어 있다. 경유지(임의의 지점)만 달라질 뿐.
경유지에서 고려대로 가는 경로는 고려대에서 경유지로 갈 때와 같다. 그러므로 집(1번)에서 다익스트라 1번, 고려대(N번)에서 다익스트라 1번 돌려주면 된다. 이렇게 하면, 낮은 곳에서 높은 곳으로만 갈 수 있다는 일반성도 잃지 않게 되므로 그래프에 간선을 추가할 때 낮은 곳에서 높은 곳으로 이어지는 단방향 간선만 추가해주면 된다.

코드

• C++

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, int> pli;

const int MAXN = 100000;
const ll inf = 1e12;

vector<pii> graph[MAXN];

void dijkstra(int start, ll *dist){
    priority_queue<pli, vector<pli>, greater<pli>> pq; pq.push({0, start});
    dist[start] = 0;
    while (!pq.empty()){
        auto [d, i] = pq.top(); pq.pop();
        if (dist[i] < d) continue;
        for (auto [j, n]: graph[i]) if (dist[j] > d + n){
            dist[j] = d + n;
            pq.push({dist[j], j});
        }
    }
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int N, M, D, E; cin >> N >> M >> D >> E;

    int h[N];
    for (int i = 0; i < N; i++) cin >> h[i];

    for (int i = 0, a, b, n; i < M; i++){
        cin >> a >> b >> n;
        // 낮은 곳에서 높은 곳으로
        if (h[--a] < h[--b]) graph[a].push_back({b, n});
        else graph[b].push_back({a, n});
    }

    // 집에서 출발
    ll dist1[N]; fill(dist1, dist1 + N, inf);
    dijkstra(0, dist1);

    // 고려대로 도착 = 고려대에서 출발
    ll dist2[N]; fill(dist2, dist2 + N, inf);
    dijkstra(N - 1, dist2);

    // 모든 도착 가능한 지점의 가치를 계산하여 최댓값을 출력
    ll result = -inf;
    for (int i = 1; i < N - 1; i++)
        if (dist1[i] < inf && dist2[i] < inf)
            result = max(result, h[i] * E - (dist1[i] + dist2[i]) * D);
    if (result > -inf) cout << result;
    else cout << "Impossible";
}

• Python

import sys; input = sys.stdin.readline
from math import inf
from heapq import heappop, heappush

def dijkstra(start, dist):
    pq = [(0, start)]
    dist[start] = 0
    while pq:
        d, i = heappop(pq)
        if dist[i] < d:
            continue
        for j, n in graph[i]:
            if dist[j] > d + n:
                dist[j] = d + n
                heappush(pq, (dist[j], j))

N, M, D, E = map(int, input().split())
h = list(map(int, input().split()))

graph = [[] for _ in range(N)]
for _ in range(M):
    a, b, n = map(int, input().split())
    a -= 1; b -= 1

    if h[a] < h[b]: # 낮은 곳에서 높은 곳으로
        graph[a].append((b, n))
    else:
        graph[b].append((a, n))

# 집에서 출발
dist1 = [inf] * N
dijkstra(0, dist1)

# 고려대로 도착 = 고려대에서 출발
dist2 = [inf] * N
dijkstra(N - 1, dist2)

# 모든 도착 가능한 지점의 가치를 계산하여 최댓값을 출력
result = -inf
for i in range(1, N - 1):
    if dist1[i] < inf and dist2[i] < inf:
        result = max(result, h[i] * E - (dist1[i] + dist2[i]) * D)
print(result) if result > -inf else print('Impossible')