[BOJ 16681] 등산

문제

BOJ 16681 등산

유형

• 다익스트라

풀이

시작위치와 고려대에서 각각 다익스트라를 써서 목표지점까지의 최단 거리를 찾고 시작위치와 고려대에서 각각 갈 수 있는 목표지점 중에서 성취도(E) 목표지점 높이 - 거리 D 값이 최대가 되는 점을 찾을면 된다.

위상정렬로도 풀 수 있다고 한다.

일반적인 다익스트라를 쓰게되면 TLE가 발생하고 약간의 최적화가 필요하다

if(cost > dist[now]) continue;

cost 저번 연산에서 구한 현재 지점의 최단거리이고 dist[now]는 다른 연산에 의해서 갱신되었을 수도 있는 현재 지점의 최단거리이다. 만약 다른 연산으로 인해 현재 지점의 최단거리가 갱신되었다면 넘기고 다른 지점으로 넣어간다.

코드

#include <bits/stdc++.h>

const int dx[4] = { 1,0,-1,0 };
const int dy[4] = { 0,-1,0,1 };

using namespace std;
int n, m, d, e;
vector<int> height(100001);
vector<pair<int, int>> adj[100001];

void solve(int start, vector<long long>& dist) {
	priority_queue<pair<long long, int>> pq;
	dist[start] = 0;
	pq.emplace( 0, start );
	while (!pq.empty()) {
		long long cost = -pq.top().first;
		int now = pq.top().second;
		pq.pop();

		if (cost > dist[now]) continue;

		for (auto x : adj[now]) {
			int next = x.second;
			int ncost = x.first;

			if (height[now] < height[next] && dist[next] > dist[now] + ncost) {
				dist[next] = dist[now] + ncost;
				pq.emplace( -dist[next], next );
			}
		}
	}
}

int main() {
	cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(false);
	cin >> n >> m >> d >> e;

	for (int i = 1; i <= n; i++) {
		cin >> height[i];
	}
	for (int i = 0; i < m; i++) {
		int a, b, c; cin >> a >> b >> c;
		if (height[a] > height[b]) swap(a, b);
		adj[a].emplace_back( c, b );
	}


	vector<long long> dist1(100001, INT64_MAX);
	vector<long long> dist2(100001, INT64_MAX);
	solve(1, dist1);
	solve(n, dist2);

	long long ans = INT64_MIN;
	for (int i = 2; i < n; i++) {
		if (dist1[i] == INT64_MAX || dist2[i] == INT64_MAX) continue;
		ans = max(ans, (long long)height[i] * e - (dist1[i] + dist2[i]) * d);
	}

	if (ans == INT64_MIN) cout << "Impossible\n";
	else cout << ans;

	return 0;
}