백준13308 주유소

작성일 | In

문제 링크

  • http://icpc.me/13308

문제 출처

  • 2016 KOI 전국 본선 고등부2

사용 알고리즘

  • Dijkstra, DP

시간복잡도

  • O(m log n)

풀이

그래프가 주어지고 최단 거리 비슷한 것을 찾는 문제입니다.
최단 거리 비슷한 것이라 말한 이유는 노드에도 가중치가 있고, 계속 간선과 노드의 가중치를 곱하기 때문입니다.

만약 그래프나 트리가 아니고, 아래 사진과 같이 선형으로 이루어져 있다고 생각해봅시다.

(그림 1)

이런 경우만 생각한다면 문제 해결은 매우 쉬워집니다.
dp[i]를 i번 도시까지 가기 위한 최소 기름 값, node[i]를 i번 도시의 기름 값, dist[i, j]를 i번 도시에서 j번 도시로 가는 최단 거리라고 합시다.
이 때, dp[i] = min(dp[k] + dist[k, i] * node[k]) 라는 점화식을 세울 수 있습니다. (단, 1 <= k < i)
dist를 dijkstra algorithm으로 미리 구해놓으면, O(m log n)에 문제를 해결할 수 있습니다. 대회 당시에는 이 경우가 2번 서브테스크였습니다.

다시 원래 문제로 돌아와서, 위에서 쓴 아이디어를 변형하여 원래 문제에 적용시켜봅시다.
dijkstra를 구현할 때 priority_queue에는 대개 {거리, 다음 노드} 형태의 데이터를 집어넣게 됩니다. 이 문제에서는 지금까지 지나오면서 가장 기름 값이 싼 도시를 추가로 넣을 것입니다.
현재 노드까지의 비용을 nowDist, 다음 노드를 idx, 가장 기름 값이 싼 도시의 기름 값을 cost라고 합시다.
dp[i][j]를 j에서 마지막으로 기름을 구매해서 i까지 가는 최소 비용이라고 정의하면, dp[nxt][min(cost, node[nxt])] = nowDist + dist[now, nxt] * cost 와 같은 점화식을 이용해 DP Table을 채울 수 있고, dp[n][1~n]중 최소값이 정답이 됩니다.
이 때 가능한 상태는 최대 n개이므로 최종 시간 복잡도는 O(n2)이 됩니다.

그러나 priority_queue는 항상 최대 혹은 최소값만 pop 한다는 점을 생각하면, dijkstra를 돌리는 도중 n번 노드에 처음 도달한 경우가 최소 비용임을 알 수 있습니다.
이 점을 이용하면 조금 더 쉽게 구현이 가능하고, 시간 복잡도도 O(m log n)으로 줄일 수 있습니다.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> p;

struct asdf {
	ll node, cost, dst;
	asdf(int a, int b, ll c) : node(a), cost(b), dst(c) {}
	bool operator < (asdf r) const { return dst > r.dst; }
};

bool chk[3000][3000];
ll n, m, node[3000];
vector<p> g[3000];


ll dijkstra(){
	priority_queue<asdf> pq;
	pq.push(asdf(1, node[1], 0));
	while (!pq.empty()) {
		asdf now = pq.top();
		ll idx = now.node, cost = now.cost, dist = now.dst;
		pq.pop();
		if (chk[idx][cost]) continue;
		if (idx == n) return dist;

		chk[idx][cost] = 1;
		for (auto nxt : g[idx]){
			pq.push(asdf(nxt.first, min(cost, node[nxt.first]), cost*nxt.second + dist));
		}
	}
}

int main() {
	cin >> n >> m;
	for (int i = 1; i <= n; i++) cin>>node[i];
	for (int i = 0; i < m; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		g[a].push_back({b, c});
		g[b].push_back({a, c});
	}

	cout << dijkstra();
}