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

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

1162번: 도로포장

백준 1162번 도로포장 문제를 풀었다.

 

간선의 가중치가 모두 양수이고 특정 노드까지의 최단 비용을 구하는 문제라서 다익스트라를 사용해야겠다고 생각했다.

기본적인 다익스트라 문제에서 추가된 것은 도로가 포장될 수 있다는 점이다. 따라서 노드 구조체에 포장된 도로의 개수를 저장하는 paved 변수를 추가해서 사용했다.

 

dist[i][j] 배열은 포장된 도로의 개수가 i 개일 때, j 도시까지 가는 최단 비용을 저장하는 배열이다.

dist[i][j]	1	2	3	4
0	0	10	1	20
1	0	0	0	1
2	0	0	0	0

예제를 기준으로 dist[0][k] 배열은 포장된 도로의 개수가 0이므로 다익스트라를 그냥 실행했을 때의 결과값을 저장한다.

dist[1][k] 배열은 포장된 도로의 개수가 1일 때 각 도시까지 가는 최단 비용을 저장한다.

 

우선순위 큐 top 노드의 인접 노드를 순회하면서 도로를 포장하지 않을 경우와 포장한 경우 둘 다 우선순위 큐에 넣어줬다.

 

주의해야할 점은 도로 비용이 최대 1,000,000 이므로 long long 변수를 사용해야 하는 것이다.

또한 1번 노드에서 N번 노드까지 가는 도로의 개수가 k보다 작다면 제대로 된 답을 출력하지 않는다.

 

 

아래는 전체 코드입니다.

#include <iostream>
#include <string>
#include <vector>
#include <queue>
#pragma warning(disable:4996)

using namespace std;

#define INF 1000000000
#define LLINF 9223372036854775800

typedef long long ll;

struct Node {
	int end;
	ll cost;
	int paved;
};

struct compare {
	bool operator()(Node a, Node b) {
		return a.cost > b.cost;
	}
};

int n, m, k;
vector<Node> v[10001];
vector<ll> dist[21];

void Dijkstra() {
	priority_queue<Node, vector<Node>, compare> pq;
	for (int i = 0; i < 21; i++) {
		dist[i].assign(n + 1, LLINF);
		dist[i][1] = 0;
	}
	pq.push({ 1,dist[0][1],0 });

	while (!pq.empty()) {
		Node temp = pq.top();
		int cur = temp.end;
		ll cost = temp.cost;
		int paved = temp.paved;
		pq.pop();
		if (dist[paved][cur] < cost)
			continue;
		for (int i = 0; i < v[cur].size(); i++) {
			temp = v[cur][i];
			int next = temp.end;
			ll next_cost = cost + temp.cost;		

			if (dist[paved][next] > next_cost) {
				dist[paved][next] = next_cost;
				pq.push({ next,next_cost, paved });
			}

			if (paved < k) {
				next_cost = cost + 0;
				paved++;
				if (dist[paved][next] > next_cost) {
					dist[paved][next] = next_cost;
					pq.push({ next,next_cost,paved });
				}
				paved--;
			}
		}
	}
}

int main() {
	cin >> n >> m >> k;
	for (int i = 0; i < m; i++) {
		int start, end, cost;
		scanf("%d %d %d", &start, &end, &cost);
		v[start].push_back({ end,cost });
		v[end].push_back({ start,cost });
	}

	Dijkstra();

	ll min_cost = LLINF;
	for (int i = 0; i <= k; i++) {
		if (min_cost > dist[i][n])
			min_cost = dist[i][n];
	}
	cout << min_cost;

	return 0;
}