백준 16681 - 등산(C++)

문제 링크입니다. https://www.acmicpc.net/problem/16681

16681번: 등산

다익스트라를 양쪽에서 이용해 푸는 문제입니다.

목표 지점을 정해, 집에서 목표지점까지는 높이를 무조건 올라가게, 목표지점부터 고려대학교까지는 높이를 무조건 내려가는 방식으로 할 때,
얻을 수 있는 최대 가치는 얼마인지 구하는 문제입니다.

N의 갯수가 100,000이기에, 목표지점 하나마다 경우를 확인해보기에는 경우가 많아 시간초과가 됩니다.

따라서, 시작지점과 끝점에서 시작에 다른 정점들까지의 최소 거리를 전부 구하고, 두 값들의 합을 비교해서 최소 값을 가져오면 됩니다.
주의할 점은 음수의 값도 나올 수 있기에 비교하는 변수의 값을 최솟값으로 잡고 시작해야한다는 점입니다.

다익스트라의 시작을 1번과 N번으로 한다면, 1->목표지점이나, N->목표지점이나 항상 높이가 증가하는 곳으로 가는 것은 같습니다.
따라서 다익스트라를 2개 구현할 필요는 없습니다.



자세한 것은 코드를 참고해주세요.

#define _CRT_SECURE_NO_WARNINGS
#include <cstring>
#include <vector>
#include <iostream>
#include <algorithm>
#include <queue>
#include <cmath>
#include <cstdio>
#include <climits>
#define INF LLONG_MAX
#define F first
#define S second

using namespace std;

int N, M, D, E;
vector<pair<int, int>> connect[100001];
long long Distance[100001];
long long Dis_up[100001];
long long Dis_down[100001];
int height[100001];
priority_queue<pair<long long, int>> q;

void reset_distance(){
	for(int i = 1; i <= N; i++) Distance[i] = INF;
}

void Dijstra(int st){
	reset_distance();
	Distance[st] = 0;
	q.push({-0, st});
	while(!q.empty()){
		int x = q.top().S;
		long long cost = -q.top().F;
		q.pop();
		if(Distance[x] < cost) continue;
		for(int i = 0; i < connect[x].size(); i++){
			int xx = connect[x][i].F;
			long long n_cost = cost + connect[x][i].S;
			if(height[xx] <= height[x]) continue;
			if(Distance[xx] > n_cost){
				Distance[xx] = n_cost;
				q.push({-Distance[xx], xx});
			}
		}
	}
}

void solve(){
	Dijstra(1);
	for(int i = 1; i <= N; i++){
		Dis_up[i] = Distance[i];
	}
	Dijstra(N);
	for(int i = 1; i <= N; i++){
		Dis_down[i] = Distance[i];
	}
	long long ans = -INF;
	for(int i = 2; i <= N-1; i++){
		if(Dis_up[i] == INF || Dis_down[i] == INF) continue;
		long long sum = 0;
		sum = height[i] * E - (Dis_up[i] + Dis_down[i]) * D;
		ans = max(ans, sum);
	}		
	if(ans == -INF) cout << "Impossible";
	else cout << ans;
}

int main() {
	cin.tie(0);
	cout.tie(0);
	cin >> N >> M >> D >> E;
	for(int i = 1; i <= N; i++) cin >> height[i];
	for(int i = 1; i <= M; i++){
		int x, y, cost;
		cin >> x >> y >> cost;
		connect[x].push_back({y, cost});
		connect[y].push_back({x, cost});
	}
	solve();
	return 0;
}

질문 및 조언은 댓글을 남겨주세요.