취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 16681번 문제인 등산이다.
문제는 아래 링크를 확인하자.

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

모든 등산경로는 가장 높은 도달지점이 존재하므로, 각 등산경로는 (집 - 가장 높은 도달지점) 부분의 오르막 부분과 (가장 높은 도달지점 - 고려대학교)의 내리막 부분으로 나눌 수 있다. 여기서 (가장 높은 도달지점 - 고려대학교)의 내리막 부분의 거리는 그 순서를 뒤집어 (고려대학교 - 가장 높은 도달지점)의 오르막 부분의 거리와 같다는 점을 이용해 문제를 풀이할 것이다.

어떤 한 지점을 가장 높은 도달지점으로 삼는 경로의 가치의 최댓값은 "집에서 해당 도달지점까지의 (오르막으로만 구성된) 최단거리와 고려대학교에서 해당 도달지점까지의 (오르막으로만 구성된) 최단거리의 합"의 최솟값을 찾아 계산해낼 수 있다. dijkstra 알고리즘을 두 번 이용해 각 지점마다 집 및 고려대학교에서 오르막만을 이용해 도달할 수 있는 최단거리를 계산해 문제를 해결하자.

등산의 가치의 최댓값이 음수가 될 수 있음에 유의하자.

아래는 제출한 소스코드이다.

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
typedef long long ll;

ll N, M, D, E;
ll h[100001];
vector<pair<int, ll>> G[100001];
ll dist1[100001], dist2[100001];

void dijkstra1() {
	dist1[1] = 1;
	priority_queue<pair<ll, int>> pq;
	pq.push(make_pair(-1, 1));

	while (!pq.empty()) {
		ll d = -pq.top().first; int cur = pq.top().second; pq.pop();
		if (dist1[cur] < d) continue;
		for (auto& p : G[cur]) {
			int nxt = p.first; ll dd = d + p.second;
			if (dist1[nxt] == 0 || dd < dist1[nxt]) {
				dist1[nxt] = dd, pq.push(make_pair(-dd, nxt));
			}
		}
	}
}

void dijkstra2() {
	dist2[N] = 1;
	priority_queue<pair<ll, int>> pq;
	pq.push(make_pair(-1, N));

	while (!pq.empty()) {
		ll d = -pq.top().first; int cur = pq.top().second; pq.pop();
		if (dist2[cur] < d) continue;
		for (auto& p : G[cur]) {
			int nxt = p.first; ll dd = d + p.second;
			if (dist2[nxt] == 0 || dd < dist2[nxt]) {
				dist2[nxt] = dd, pq.push(make_pair(-dd, nxt));
			}
		}
	}
}

ll ans = -1000000000000000000LL;

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

	cin >> N >> M >> D >> E;
	for (int i = 1; i <= N; i++) cin >> h[i];
	while (M--) {
		int x, y; ll d; cin >> x >> y >> d;
		if (h[x] < h[y]) G[x].emplace_back(make_pair(y, d));
		else if (h[x] > h[y]) G[y].emplace_back(make_pair(x, d));
	}

	dijkstra1();
	dijkstra2();

	for (int i = 1; i <= N; i++) {
		if (dist1[i] > 1 && dist2[i] > 1) {
			ans = max(ans, h[i] * E - (dist1[i] + dist2[i] - 2) * D);
		}
	}

	if (ans == -1000000000000000000LL) cout << "Impossible";
	else cout << ans;
}