[BOJ-1162] 도로포장(C++)

백준 1162 도로포장

 

1162번: 도로포장

 

문제 설명

 

 - 도시 N개가 주어진다.

 

 - 도시와 도시 사이 도로를 통과할 때 걸리는 시간이 주어진다.

 

 - K개 이하의 도로를 포장할 수 있다. 포장을 하게 되면, 걸리는 시간은 0이 된다.

 

 - K개 이하로 도로를 포장하여 1번 도시에서 N번 도시까지 최단 시간을 구하라

---

 

입력 값

 

 - 첫 줄에는 도시의 수 N 과 도로의 수 M 과 포장할 도로의 수 K가 공백으로 구분되어 주어진다.

   ( 1<= N <= 10,000) / ( 1<= M <= 50,000) /  ( 1<= K <= 20)

 

 - 이후 M개의 줄에는 도로를 연결 짓는 두 도시와 도로를 통과하는데 걸리는 시간이 주어진다.

 

 - 도로는 양방향 도로이다.

 

 - 걸리는 시간은 100만보다 작거나 같은 자연수이다.

---

 

 

예제

 

---

 

 

문제 분석

 

 - 1번 도시에서 N번 도시까지 가는 최단 시간을 구하는 문제이다.

 

 - 다만, 도로를 K번 포장하여, 도로의 시간을 0으로 만들 수 있다.

 

 - 이 문제를 접근하는 방법은 해당 도시까지 도착하는 최단 경로를 찾는데,

  포장을 몇 번 했는지에 따라 나누어서 모두 계산해야 한다는 것이다.

 

 - 즉, 1번에서 3번 도시까지 오는 경우 포장을 0번, 1번, 2번, ... K번 까지 모두 다른 경우로 판단해야 한다는 것이다.

 

 - 그렇기 때문에 다익스트라 + 메모이제이션을 이용하여 풀 수 있다.

 

 - 주의사항으로 각 도로는 최대 100만이기 때문에, 모든 도시를 한 번씩 거쳐서 올 경우 

   N의 최대값 x 100 만 = 1만 x 100만 = 100억이 된다. 즉, int가 아닌 long long을 사용해야 한다.

---

 

 

소스 코드

 

#include <bits/stdc++.h>

using namespace std;

long long dist[21][10001];

int N, M, K;

vector<pair<int, int>> road[10001];

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> N >> M >> K;
	fill(&dist[0][0], &dist[0][0] + 21 * 10001, LLONG_MAX);

	// 1번 도로(시작점)에서 시작하는 경우는 거리가 무조건 0이 된다.
	for (int i = 0; i < 21; i++) {
		dist[i][1] = 0;
	}


	for (int i = 0; i < M; i++) {
		
		int a, b, c;
		cin >> a >> b >> c;

		road[a].push_back({ b,c });
		road[b].push_back({ a,c });
	}

	// 거리, k, 노드
	priority_queue<tuple<long long, int, int>> pq;
	pq.push({ 0,0,1 });

	while (!pq.empty()) {
		long long nowCost = -get<0>(pq.top());
		int nowK = get<1>(pq.top());
		int nowIndex = get<2>(pq.top());


		pq.pop();

		if (dist[nowK][nowIndex] < nowCost) {
			continue;
		}

		for (auto next : road[nowIndex]) {

			int nextIndex = next.first;
			long long nextCost = next.second;
			int nextK = nowK + 1;

			// 도로를 포장하지 않은 경우
			if (dist[nowK][nextIndex] > nowCost + nextCost) {
				dist[nowK][nextIndex] = nowCost + nextCost;
				pq.push({ -dist[nowK][nextIndex] , nowK,nextIndex });
			}

			// 도로를 포장한 경우
			if (nextK <= K && dist[nextK][nextIndex] > nowCost) {
				dist[nextK][nextIndex] = nowCost ;
				pq.push({ -dist[nextK][nextIndex] , nextK,nextIndex });
			}

		}


	}

	long long result = LLONG_MAX;

	for (int i = 0; i < 21; i++) {
		result = min(result, dist[i][N]);
	}
	
	cout << result << endl;
	


	return 0;
}