취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 13308번 문제인 주유소이다.
문제는 아래 링크를 확인하자.

https://www.acmicpc.net/problem/13308 

1번 노드에서 막 출발했을 때를 기준으로, 각 순서쌍 "(주어진 그래프의 노드, 해당 노드까지 도착하는 과정에서 등장하는 최소 주유기름값)"들을 노드로 갖고, 원본 그래프의 연결관계를 이용해 각 순서쌍에서 다음 순서쌍으로 될 수 있는 관계들을 에지로 갖는 새로운 그래프를 생각하자. 이 때 각 에지의 가중치는 (출발 노드까지 도달할 때의 최소 주유 기름값) * (원래 그래프의 에지의 가중치(거리))가 될 것이다.

위 그래프에서 dijkstra를 이용하고, N번 노드까지 도착하는 각 경우의 이동거리 중 최솟값을 찾아내 출력하자. 노드 N^2개, 에지는 NM개 있으므로 시간복잡도는 O(NMlgN)이 된다.

아래는 제출한 소스코드이다.

#include <iostream>
#include <queue>
#include <vector>
using namespace std;
typedef long long ll;

int N, M;
vector<pair<int, ll>> G[2501]; // {노드, 거리}
priority_queue<pair<ll, pair<int, int>>> pq; // {-거리, {노드, 기름단위가격 사용중인 주유소번호}
ll oil[2501];
ll dist[2501][2501];
ll distbest[2501]; int distoil[2501];

void dijkstra() {
	for (int i = 1; i <= N; i++) {
		distbest[i] = 1000000000000000007LL;
		for (int j = 1; j <= N; j++) dist[i][j] = 1000000000000000007LL;
	}
	dist[1][1] = 1;
	pq.push(make_pair(-1, make_pair(1, 1)));
	while (!pq.empty()) {
		ll d = -pq.top().first; int cur = pq.top().second.first, p = pq.top().second.second; pq.pop();
		if (dist[cur][p] < d) continue;
		ll& price = oil[p];

		for (auto& node : G[cur]) {
			int nn = node.first;
			int pp = (oil[p] > oil[nn]) ? nn : p;

			ll dd = d + price * node.second;
			if (dist[nn][pp] <= dd || (distbest[nn] <= dd && oil[distoil[nn]] <= price)) continue;
			dist[nn][pp] = dd;
			if (distbest[nn] > dd) distbest[nn] = dd, distoil[nn] = pp;
			pq.push(make_pair(-dd, make_pair(nn, pp)));
		}
	}
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> N >> M;
	for (int n = 1; n <= N; n++) cin >> oil[n];
	while (M--) {
		int x, y; ll d; cin >> x >> y >> d;
		G[x].emplace_back(make_pair(y, d));
		G[y].emplace_back(make_pair(x, d));
	}

	dijkstra();

	cout << distbest[N] - 1;
}