[C++] 백준 1162번: 도로포장

문제 링크

1162번: 도로포장

문제 요약

1번 정점에서 N번 정점으로 이동하는데, 최대 K번 도로를 포장할 수 있다. 포장된 도로를 이동하는데는 시간이 0만큼 걸린다. 1번 정점에서 N번 정점으로 이동하는데 걸리는 시간의 최솟값을 구해야 한다.

접근 방법

거리를 저장하는 dist배열을 2차원으로 선언해주면 간단하게 풀리는 문제입니다. dist[N]과 같이 선언했다면 dist[K][N]과 같이 선언해주면 됩니다.

다익스트라를 돌리면서, 현재 도로포장을 사용한 횟수가 K 미만이라면, 인접한 정점을 무비용으로 방문하는 대신, 도로포장 사용횟수를 1 증가시켜 우선순위큐에 넣습니다. 물론, 도로포장을 사용하지 않는 경우도 우선순위큐에 넣어줍니다. 이렇게 다익스트라를 다 돌린 뒤에, N번 정점에서 0부터 K까지 dist 배열의 최솟값을 출력해주면 간단하게 풀립니다.

무척 웰노운인 문제이고 읽자마자 풀이를 떠올렸지만 변수명을 헷갈리게 지었다가 실수를 많이해서 많이 틀렸습니다.

코드

#include <bits/stdc++.h>

using namespace std;

const int MAX = 10001;
const long long INF = LLONG_MAX;
int n, m, k;
long long dist[21][MAX];
vector<pair<int, long long>> adj[MAX];

struct Data {
	int v, cnt;
	long long d;
};

struct Compare {
	bool operator()(const Data& a, const Data& b) {
		return a.d > b.d;
	}
};

void init(void) {
	for (int i = 0; i <= k; i++)
		for (int j = 1; j <= n; j++)
			dist[i][j] = INF;
}

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

	cin >> n >> m >> k;

	init();

	for (int i = 0; i < m; i++) {
		int u, v;
		long long l;
		cin >> u >> v >> l;
		adj[u].push_back({ v, l });
		adj[v].push_back({ u, l });
	}

	priority_queue<Data, vector<Data>, Compare> pq;
	dist[0][1] = 0;
	pq.push({1, 0, 0});

	while (!pq.empty()) {
		auto now = pq.top();
		pq.pop();

		if (now.d > dist[now.cnt][now.v])
			continue;

		for (auto& next : adj[now.v]) {
			if (now.cnt != k && dist[now.cnt + 1][next.first] > now.d) {
				dist[now.cnt + 1][next.first] = now.d;
				pq.push({ next.first, now.cnt + 1, now.d });
			}

			if (dist[now.cnt][next.first] > now.d + next.second) {
				dist[now.cnt][next.first] = now.d + next.second;
				pq.push({ next.first, now.cnt, now.d + next.second });
			}
		}
	}

	long long ans = INF;
	for (int i = 0; i <= k; i++)
		ans = min(ans, dist[i][n]);

	cout << ans << '\n';
	return 0;
}