[백준] 등산 (16681번)

문제

주환이는 요즘 등산에 빠졌다. 주환이는 등산을 위해 지도를 가지고 있는데, 그 지도에는 각 지점의 높이와 갈 수 있는 다른 지점까지의 거리가 표시되어 있다.

주환이는 아침에 집에서 출발하여 등산을 갔다가, 오후 수업을 듣기 위해 고려대학교로 돌아와야 한다.

1. 주환이는 지도의 임의의 지점을 골라, 그 지점을 목표로 정한다. 집 또는 고려대학교는 목표로 선택할 수 없다.
2. 주환이가 집에서 정한 목표에 도달할 때 까지는 항상 높이가 증가하는 방향으로만 이동해야 한다.
3. 주환이가 정한 목표에 도달한 후, 고려대학교로 갈 때에는 항상 높이가 감소하는 방향으로만 이동해야 한다.
4. 주환이는 거리 1을 움직일 때 마다 D 의 체력이 소모된다.
5. 주환이는 정한 목표에 도달하면 높이 1당 E 의 성취감을 얻는다. 즉 높이가 h인 목표에 도달하면 hE의 성취감을 얻는다.

주환이는 이 등산의 가치를 (얻은 성취감) - (소모한 체력) 으로 계산하기로 하였다. 주환이를 위해 가치가 가장 높은 등산 경로를 선택해주자.

입력

첫 번째 줄에 지도에 표시된 지점의 개수, 지점을 잇는 경로의 개수, 주환이의 거리 비례 체력 소모량, 높이 비례 성취감 획득량을 나타내는 정수 N, M, D, E가 공백을 사이에 두고 주어진다. (2 ≤ N ≤ 100,000, 1 ≤ M ≤ 200,000, 1 ≤ D ≤ 100, 1 ≤  E ≤ 100)

두 번째 줄에 N개의 정수 h1, ...  ,hN이 공백으로 구분되어 주어진다. hi는 i 번째 지점의 높이를 의미한다. (1 ≤ hi ≤ 1,000,000, 1 ≤ i ≤ N)

세 번째 줄부터 M개의 줄에 걸쳐 세 정수 a, b, n이 공백으로 구분되어 주어진다. 이는 a번 지점과 b번 지점을 잇는 거리 n의 양방향 경로가 있음을 의미한다. (1 ≤ a, b ≤ N, 1 ≤ n ≤ 100,000)

어떤 지점에서 다른 지점으로 가는 경로가 여러 개 있을 수도 있으며 (등산로는 여러 개가 있을 수 있다), 한 지점에서 출발해 그 지점으로 돌아가는 경로가 있을 수도 있다 (쉼터에서 몇 바퀴 돌며 쉴 수도 있다).

주환이의 집은 1번 지점에 위치하고, 고려대학교는 N번 지점에 위치하며 주환이의 집과 고려대학교의 높이는 1임이 보장된다.

출력

첫 번째 줄에 주환이가 얻을 수 있는 가치의 최댓값을 출력한다. 만약 조건을 만족하는 등산 경로를 선택할 수 없다면, "Impossible"을 쌍따옴표를 제외하고 출력한다. 답이 음수일 수 있음에 유의하여라.

예제 입력 1 복사

8 13 4 9 1 4 7 3 10 2 15 1 1 2 3 3 4 2 5 6 6 7 8 2 2 3 4 6 7 2 3 6 1 4 8 3 5 1 6 8 3 5 2 5 4 4 6 3 5 3 8

예제 출력 1 복사

15

---

 

또다른 등산 문제이다. 

1 지점에서 x 지점으로 등산한 후 N으로 하산했을 때 최대의 가치를 구하면 된다.

 

1을 시작점으로 하는 등산 다익스트라를 한 번 계산한 후

N을 시작점으로 하는 등산 다익스트라를 다시 실행하면 된다.

N에서 등산을 하는 이유는 2, 3, 4, ... x 지점에서 N으로 하산하는 계산을 매번 하기 번거롭기 때문에 N에서 2, 3, 4, ... x지점으로 등산하는 거리 계산을 통해 단축시키는 것이다.

 

주의할 점은 거리 계산이 int 범위를 넘을 수 있으므로 거리와 관련된 모든 부분을 long long 으로 선언해야 한다.

 

 

코드 원본 : https://github.com/chosh95/STUDY/blob/master/BaekJoon/2020/%EB%93%B1%EC%82%B0%20(16681%EB%B2%88).cpp

chosh95/STUDY

 

C++ 코드

#include <iostream>
#include <queue>
#include <algorithm>
#include <vector>
using namespace std;
const long long INF = 1000000000000;
int N, M, D, E;
long long height[100001];
long long asc[100001]; //등산 거리 기록
long long des[100001]; //하산 거리 기록
vector<pair<int, int>> adj[100001]; //adj[a] = (b,n) : a에서 b까지 n의 거리

void dijk(int start, long long visit[]) {
	priority_queue<pair<long long, int>,vector<pair<long long,int>>, greater<pair<long long,int>>> q;
	q.push({ 0,start }); // 시작지점에서 0의 거리로 출발
	visit[start] = 0;

	while (!q.empty()) {
		long long cost = q.top().first; //현재까지 이동 거리
		int cur = q.top().second; //현재 지점
		q.pop();

		if (cost > visit[cur]) continue; //중복 제거

		for (int i = 0; i < adj[cur].size(); i++) {
			long long nextDist = adj[cur][i].second; //다음 지점까지 거리
			int nextPos = adj[cur][i].first; //다음 이동 지점
			if (height[cur] >= height[nextPos]) continue;
			if (visit[nextPos] > cost + nextDist) {
				visit[nextPos] = cost + nextDist;
				q.push({ cost + nextDist,nextPos });
			}
		}
	}
}

int main()
{
	cin >> N >> M >> D >> E;

	for (int i = 1; i <= N; i++) {
		cin >> height[i];
		asc[i] = des[i] = INF;
	}

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

	dijk(1,asc); //1에서 등산하는 거리 기록
	dijk(N, des); //N에서 등산하는 거리 기록 -> 결과적으로 x에서 N으로 하산

	long long res = -INF;
	for (int i = 2; i < N; i++) {
		if (asc[i] == INF || des[i] == INF) continue; //등, 하산 불가 지점 제외
		long long cost = height[i] * E - D * (asc[i] + des[i]);
		res = max(cost, res);
	}

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