BOJ 16681 등산

역시나 오늘도 문제를 풀었고, 역시나 오늘도 고통을 받았다. (아니 왜 하던 걸 못해)

시간이 없으니(시계톡톡) 바로 오답을 시작한다ㅏㅏㅏ....

 

1. 문제 설명

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

16681번: 등산

작년 고대 KCPC Intermediate 문제이다. 문제를 간단히 요약하자면 1 → k → N으로 가는 최단 경로를 찾아야 하는데 1 → k는 오르막길 k → N은 내리막길이어야 하고 구해야 하는 값은 height[k] * E - dist[k] * D의 max 값을 찾아야 한다. 어떻게 해도 경로를 만들 수 없으면 Impossible을 출력하면 된다. 이게 등산의 가치란다 ㅎ

 

2. 아이디어

구해야 하는 값을 다시 보자.

height 값은 input으로 주어지기 때문에 우리가 알아야 하는 것은 dist만 알면 된다! E, D 이런 것도 다 상수로 input에 주어진다.

 

하지만 문제의 조건에서 약간의 애로사항이 꽃핀다. 즉 k까지 갈 때는 오르막길, k에서 N으로 갈 때는 내리막길이어야 한다는 것. 그래서 나는 문제를 반으로 나누기로 했다. 하나는 1에서 k로 가는 길, 나머지는 k에서 N으로 가는 길을 찾는 것으로 나눴다. 후자를 다르게 생각하면 N에서 출발하여 모든 목적지에 대해 오르막길을 찾아도 된다.(어짜피 양방향 간선이기 때문에) 아이디어를 종합해보자면, 1과 N에서 각각 Single Source Multiple Destination Shortest path를 찾는 문제이다. 물론 오르막길이라는 조건이 있기는 하지만.

 

그렇다. 이 문제는 다익스트라 두 번으로 해결할 수 있는 문제이다. 근데 이걸 알고도 13번이나 틀렸는데 이것보다 경계값이나 값의 범위가 나에게는 문제였던 것 같다 ㅎ값에 대해 좀 더 얘기를 하자면 long long을 적절히 사용하지 않으면 Integer Overflow가 일어날 수 있기 때문에 INF의 값의 설정과 값들이 이동하는 자료구조나 변수에 Overflow가 일어나지 않게 조심하자.

 

또 한 가지 주목해서 볼 점은, 나 같은 경우에는 다익스트라를 구현할 때 인접 행렬을 이용한 구현방법을 많이 썼다. 하지만 이 문제에서 N의 범위는 최대 10만이고 M의 범위는 20만인 것을 확인할 수 있다. 여기서 N^2의 메모리를 할당해버리면...... 100억 바이트인데 무려 10GB정도 된다...ㅎ 그래서 인접행렬로 풀이할 수는 없고, 인접리스트와 Priority Queue를 이용하여 풀이를 해야했다. 개인적으로 익숙하지 않은 방식이긴 한데 많이 익숙해져야겠다....

 

정리해보면,

---

1. 1에서 Dijkstra 한 번.

2. N에서 Dijkstra 한 번.

3. 2부터 N-1까지 height[k] * E - dist[k] * D를 최대로 갖는 곳을 찾으면 출력, 없으면 Impossible 출력.

---

3. 소스 코드

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

#define NMAX 100002
#define INF 1000000000000
#define ll long long

int N, M, D, E, height[NMAX], a, b, n;
vector<pair<ll, ll>> graph[NMAX];

ll dist[2][NMAX];

priority_queue<pair<ll, ll>> pq;

void dijkstra(int mode) { //0: 1 to k, 1: k to N
	if (!mode) {
		dist[0][1] = 0;
		pq.push({ 0,1 });
	}
	else {
		dist[1][N] = 0;
		pq.push({ 0, N });
	}

	while (!pq.empty()) {
		ll here = pq.top().second;
		ll cost = -pq.top().first;
		pq.pop();

		if (cost > dist[mode][here]) continue;

		for (auto i : graph[here]) {
			if (cost + i.first < dist[mode][i.second] && height[i.second] > height[here]) {
				dist[mode][i.second] = cost + i.first;
				pq.push({ -dist[mode][i.second], i.second });
			}
		}
	}
}

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

	cin >> N >> M >> D >> E;
	for (int i = 1; i <= N; i++) {
		cin >> height[i];
		dist[0][i] = dist[1][i] = INF;
	}

	for (int i = 0; i < M; i++) {
		cin >> a >> b >> n;
		graph[a].push_back({ n, b });
		graph[b].push_back({ n, a });
	}

	dijkstra(0); //1 to dest
	dijkstra(1); //N to dest

	ll res = -INF;
	for (int i = 2; i < N; i++) {
		if (dist[0][i] != INF && dist[1][i] != INF) {
			res = max(res, height[i] * E - D * (dist[0][i] + dist[1][i]));
		}
	}

	if (res == -INF) cout << "Impossible\n";
	else cout << res << "\n";
}