[백준 13308] 주유소

13308번: 주유소 (acmicpc.net)

13308번: 주유소

 

다익스트라 문제이다.

이 문제를 해결할 때 특히 최소 비용이 MAX_INT 값을 넘어간다는 것을 캐치하지 못해서 많이 삽질한 문제이다.

문제를 해결함에 있어서 int 로 설정해야 할지, long long 으로 설정해야 할지 미리 파악을 해두는 것이 중요하다.

 

 

※ 문제 접근

 

① 어떠한 지점 P 에 대해서 특정 기름(oil) 으로 마지막 지점까지 도달하는데 최소 비용에 대한 배열 설계가 필요하다.

     따라서 2차원 배열로 다음과 같이 선언하였다.

cost[P][oil] = P 지점에서 oil 으로 마지막 지점까지 도달하는데 최소 비용

 

 

② 다음 지점에서의 oil 값이 현재 지점의 oil 값보다 크거나 작거나 같을 수 있다.

     케이스별로 살펴보도록 하자.

 

 

출발 지점인 1번 지점의 oil 값은 10, 2번 지점의 oil 값은 20 이다.1번 지점과 2번 지점의 거리는 c1 이므로

최소한으로 2번 지점에 도달할 수 있는 비용은 10*c1 이다.

이때, 2번 지점의 oil 값이 더 크므로 1번 지점의 oil 값을 그대로 가져가야 한다.

이 말은 즉, 2번 지점에서 다른 지점으로 갈 때 oil 값을 2번 지점의 20 으로 적용하는 것이 아니라 

1번 지점의 10 을 적용해야 한다는 것이다.

 

 

이번엔 출발 지점인 1번 지점과 3번 지점의 oil 값이 같은 경우다.

1번 지점과 3번 지점의 거리는 c2 이므로 최소한으로 3번 지점에 도달할 수 있는 비용은 10*c2 이다.

이때, 3번 지점의 oil 값과 같으로 동일하게 oil 값을 가져가면 된다.

 

 

출발 지점인 1번 지점의 oil 값은 10, 4번 지점의 oil 값은 5 이다.

1번 지점과 4번 지점의 거리는 c3 이므로 최소한으로 4번 지점에 도달할 수 있는 비용은 10*c3 이다.

이때, 1번 지점의 oil 값이 더 크므로 4번 지점의 oil 값으로 변경한 후 가져가야 한다.

이 말은 즉, 4번 지점에서 다른 지점으로 갈 때 oil 값을 1번 지점의 10 으로 적용하는 것이 아니라 

4번 지점의 5 를 적용해야 한다는 것이다.

 

 

 

이번엔 4번 지점으로 도착 후 1번 지점, 2번 지점으로 이동했을 때이다.

" cost[1][5] = 10*c3 + 5*c4 " 는 4번 지점의 oil 값에 4번 지점과 1번 지점의 거리를 곱해서 더하였다.

그리고 4번 지점의 oil 값이 더 작으므로 oil 값을 그대로 유지해서 간다는 점이다.

" cost[2][5] = 10*c3 + 5*c5 " 도 마찬가지로 4번 지점의 oil 값에 4번 지점과 2번 지점의 거리를 곱해서 더하였다.

그리고 4번 지점의 oil 값이 더 작으므로 oil 값을 그대로 유지해서 간다는 점이다.

 

 

③ 다익스트라 설계에 있어 우선순위 큐로 진행이 될 수 있도록 하였다.

우선 우선순위 큐는 다음과 같이 설계하였다.

priority_queue<pair<pair<ll, ll>, int>> PQ;
   =>   { {현재 비용, 현재 기름}, 현재 지점 } 으로 현재 비용, 현재 기름을 오름차순으로 관리

 

이 문제에서 현재 기름을 어떻게 갱신해서 가져갈지에 대해서는 ② 를 잘 따져보면 알 수 있다.

우선 cost 배열에 INF 으로 초기화 해준다. (여기서 INF 는 1e18 으로 지정)

초기화 하는 부분에서 long long 을 고려하지 못해서 약간의 삽질이 있었다.

그리고 시작지점인 1번 지점으로 현재 비용을 0, 현재 기름을 1번 지점의 기름, 그리고 1번 지점을

우선순위 큐에 넣고 cost[1][1번 지점의 기름] = 0 으로 세팅하고 시작한다.

다익스트라가 진행되는 코드를 살펴보도록 하자.

while (!PQ.empty()) {
	ll cur_cost = -PQ.top().first.first;
	ll cur_oil = -PQ.top().first.second;
	int cur = PQ.top().second;

	PQ.pop();
	if (cur_cost > cost[cur][cur_oil])
		continue;
	for (int i = 0; i < path[cur].size(); i++) {
		int next = path[cur][i].first;
		ll next_cost = cur_cost + cur_oil * path[cur][i].second;
		ll next_oil = min(cur_oil, oil[next]);

		if (next_cost < cost[next][next_oil]) {
			cost[next][next_oil] = next_cost;
			PQ.push({ {-next_cost, -next_oil}, next });
		}
	}
}

 

여기서 next_oil = min(cur_oil, oil[next]) 을 지정하는 부분이 핵심인 것 같다.

② 에서 설명했던 것 처럼 다음 지점에서 oil 을 어떤 값으로 가져갈 지에 대해서 정해줘야 한다.

즉, 현재 지점에서 가져왔던 oil 값과 다음 지점의 oil 값을 비교해서 더 저렴한 값으로 갱신을 해줘야 하고

갱신한 것을 가지고 적용을 계속 해나가야 한다는 것이다.

 

 

※ 전체 코드 

#define _CRT_SECURE_NO_WARNINGS
#include <string>
#include <math.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <queue>
#include <stack>

#define INF 1000000000
#define endl '\n'
#define ll long long

using namespace std;

int N, M;
ll oil[2501];
vector<pair<int, ll>> path[2501];
ll cost[2501][2501];

void input() {
	int from, to;
	ll dist;

	cin >> N >> M;
	for (int i = 1; i <= N; i++)
		cin >> oil[i];
	for (int i = 0; i < M; i++) {
		cin >> from >> to >> dist;
		path[from].push_back({ to,dist });
		path[to].push_back({ from, dist });
	}
}

void dijkstra(int start) {
	priority_queue<pair<pair<ll, ll>, int>> PQ;

	cost[start][oil[start]] = 0;
	PQ.push({ {0,-oil[start]}, start });
	while (!PQ.empty()) {
		ll cur_cost = -PQ.top().first.first;
		ll cur_oil = -PQ.top().first.second;
		int cur = PQ.top().second;

		PQ.pop();
		if (cur_cost > cost[cur][cur_oil])
			continue;
		for (int i = 0; i < path[cur].size(); i++) {
			int next = path[cur][i].first;
			ll next_cost = cur_cost + cur_oil * path[cur][i].second;
			ll next_oil = min(cur_oil, oil[next]);

			if (next_cost < cost[next][next_oil]) {
				cost[next][next_oil] = next_cost;
				PQ.push({ {-next_cost, -next_oil}, next });
			}
		}
	}
}

void solution() {
	ll ans = 1e18;

	fill(cost[1], cost[N + 1], 1e18);
	dijkstra(1);
	for (int i = 0; i <= 2500; i++) {
		ans = min(ans, cost[N][i]);
	}
	cout << ans;
}

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

	input();
	solution();

	return 0;
}