[백준/BOJ] 백준 13308번 : 주유소

www.acmicpc.net/problem/13308

13308번: 주유소

다익스트라 알고리즘을 이용해 문제를 해결했다. 주의해야 될 점은 현재 위치까지 총비용뿐만 아니라, 현재까지 가장 싼 주유소 가격도 고려해야 된다는 점이다 그래서 there로 갈 때 here까지 주유소 중 가장 싼 주유소에서 기름을 넣은걸로 한다.

 

코드

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

int n, m;
vector<int> oil_cost(2501);
vector<pair<int, int>> adj[2501]; //(길이,목적지)

long long Solve(int start, int dest)
{
	vector<vector<long long>> result(2501, vector<long long>(2501, numeric_limits<long long>::max())); //result[현재위치][이전 주유소중 가장 싼 기름값] = 현재 위치까지 가장 싼 가격
	priority_queue<pair<pair<long long, int>, int>> pq; //((총 비용, 현재까지 가장 싼 주유소 가격),현재위치)

	result[start][oil_cost[start]] = 0;
	pq.push(make_pair(make_pair(-0, oil_cost[start]), start));

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

		if (here_cost > result[here][here_min_oil])
			continue;

		if (here == dest)
			return here_cost;

		for (int i = 0; i < adj[here].size(); i++)
		{

			int there = adj[here][i].second;
			long long there_cost = here_cost + (long long)(adj[here][i].first*here_min_oil);
			int there_min_oil = min(here_min_oil, oil_cost[there]);

			if (result[there][there_min_oil] > there_cost)
			{
				result[there][there_min_oil] = there_cost;
				pq.push(make_pair(make_pair(-there_cost, there_min_oil), there));
			}

		}
	}

	return -1;
}

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


	cin >> n >> m;

	for (int i = 1; i <= n; i++)
	{
		int input;
		cin >> input;

		oil_cost[i] = input;
	}

	for (int i = 0; i < m; i++)
	{
		int u, v, len;

		cin >> u >> v >> len;

		adj[u].push_back(make_pair(len, v));
		adj[v].push_back(make_pair(len, u));
	}

	cout << Solve(1, n);

	return 0;
}