[백준/BOJ] 백준 16681번 : 등산

www.acmicpc.net/problem/16681

16681번: 등산

집에서 각각 지점으로 올라가는 최단경로와, 학교에서 각각 지점으로 올라가는 최단경로를 다익스트라 알고리즘을 통해서 구하고,  이를 통해 등산할 때 가치가 최대가 되는 값을 구한다.

 

코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <queue>
using namespace std;

int n, m, d, e;
vector<int> h;
vector<pair<int, int>> adj[100001]; //(비용, 지점)

long long Solve(int start, int dest)
{
	//start에서 각각 지점으로 올라가는 최단 경로를 구한다
	vector<long long> result1(n + 1, numeric_limits<long long>::max());
	priority_queue<pair<long long, int>> pq1;

	pq1.push(make_pair(-0, start));

	while (!pq1.empty())
	{
		int here = pq1.top().second;
		long long here_cost = -pq1.top().first;
		pq1.pop();

		if (result1[here] < here_cost)
			continue;

		for (int i = 0; i < adj[here].size(); i++)
		{
			int there = adj[here][i].second;
			long long there_cost = here_cost + adj[here][i].first;

			//이동하는 곳의 높이가 더 크지 않을때
			if (h[here] >= h[there])
				continue;

			if (result1[there] > there_cost)
			{
				result1[there] = there_cost;
				pq1.push(make_pair(-there_cost, there));
			}
		}
	}

	//dest에서 각각 지점으로 올라가는 최단 경로를 구한다
	vector<long long> result2(n + 1, numeric_limits<long long>::max());
	priority_queue<pair<long long, int>> pq2;

	pq2.push(make_pair(-0, dest));

	while (!pq2.empty())
	{
		int here = pq2.top().second;
		long long here_cost = -pq2.top().first;
		pq2.pop();

		if (result2[here] < here_cost)
			continue;

		for (int i = 0; i < adj[here].size(); i++)
		{
			int there = adj[here][i].second;
			long long there_cost = here_cost + adj[here][i].first;

			//이동하는 곳의 높이가 더 크지 않을때
			if (h[here] >= h[there])
				continue;

			if (result2[there] > there_cost)
			{
				result2[there] = there_cost;
				pq2.push(make_pair(-there_cost, there));
			}
		}
	}

	long long ret = numeric_limits<long long>::min();

	//각각 지점을 확인하여 등산의 가치가 최대가 되는 값을 구한다
	for (int i = 2; i <= n - 1; i++)
	{
		if (result1[i] == numeric_limits<long long>::max() || result2[i] == numeric_limits<long long>::max())
			continue;

		ret = max(ret, (long long)(h[i] * e) - (long long)((result1[i] + result2[i])*d));
	}

	return ret;
}

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	cin >> n >> m >> d >> e;

	h.push_back(0); //h 인덱스 1번부터 쓰기 위해 0번째에 그냥 0을 넣어둔다 
	for (int i = 1; i <= n; i++)
	{
		int input;
		cin >> input;

		h.push_back(input);
	}

	for (int i = 0; i < m; i++)
	{
		int a, b, dist;

		cin >> a >> b >> dist;

		adj[a].push_back(make_pair(dist, b));
		adj[b].push_back(make_pair(dist, a));
	}

	if (n == 2)
		cout << "Impossible";

	else
	{
		long long result = Solve(1, n);

		if (result == numeric_limits<long long>::min())
			cout << "Impossible";
		else
			cout << result;
	}


	return 0;
}