취미로 코딩하기

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

이번에 볼 문제는 백준 1162번 문제인 도로포장이다.
문제는 아래 링크를 확인하자.

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

(포장도로 이용 횟수, 도시번호)의 쌍을 하나의 노드로 생각하고 dijkstra 알고리즘을 이용하자.

이 때, M개의 간선을 포장도로 이용 횟수별로 하나하나 다 이으면 많은 용량을 사용해야하므로, 연결하는 도시와 거리정보로만 그래프를 구성해두고 포장도로 이용횟수는 따로 변수로 관리해 dijkstra를 진행하자.

최단거리가 될 수 없는 후보는 우선순위 큐에 넣지 않는 방식으로 휴리스틱한 최적화를 할 수 있다.

답이 32비트 정수 자료형의 범위를 넘어갈 수 있음에 유의하자. (일자그래프에 모든 가중치가 100만인 경우를 생각해보자.)

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

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

int N, M, K;
vector<pair<int, ll>> G[10001]; // {노드, 거리}
ll dist[21][10001];
ll tmpdist[21][10001];

void dijkstra() {
	priority_queue<pair<ll, pair<int, int>>> pq; // {-거리, 노드}
	pq.push(make_pair(-1, make_pair(0, 1)));

	while (!pq.empty()) {
		int curK = pq.top().second.first, cur = pq.top().second.second; ll d = -pq.top().first;
		pq.pop();
		if (dist[curK][cur]) continue;
		dist[curK][cur] = d;
		for (auto p : G[cur]) {
			ll dd = p.second, goal = p.first;
			if (tmpdist[curK][goal] == 0 || tmpdist[curK][goal] > d + dd) {
				tmpdist[curK][goal] = d + dd;
				pq.push(make_pair(-(d + dd), make_pair(curK, goal)));
			}
			if (curK < K) {
				if (tmpdist[curK + 1][goal] == 0 || tmpdist[curK + 1][goal] > d) {
					tmpdist[curK + 1][goal] = d;
					pq.push(make_pair(-(d), make_pair(curK + 1, goal)));
				}
			}
		}
	}
}

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

	cin >> N >> M >> K;
	while (M--) {
		int x, y, d; cin >> x >> y >> d;
		G[x].emplace_back(make_pair(y, d));
		G[y].emplace_back(make_pair(x, d));
	}

	dijkstra();

	ll ans = 1000000000000000007LL;
	for (int k = 0; k <= K; k++) ans = min(ans, dist[k][N]);

	cout << ans - 1;
}