백준 1162번, 도로포장 / Revamping Trails

 

 

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

1162번: 도로포장

요약

 

1번 정점에서 N번 정점으로 이동할 때 최대 K개의 가중치를 무시하여 최단경로를 찾는다.

---

1. N개의 도시와 M개의 양방향 도로로 이루어진 가중치 무방향 그래프가 주어진다.

 

2. 도로를 포장하는 경우에는 도로의 가중치가 0이 되고, 최대 K개의 도로를 포장할 수 있을 때의 최단경로는 다익스트라와 DP를 활용하여 구할 수 있다.

 

3. dist[i][j] 배열에 1번에서 i번 정점까지 j개의 도로를 포장하였을 때 최단경로를 기록한다.

 

4. 다익스트라 과정에서 도로를 포장하지 않는 경우와 도로를 포장하는 경우 두 가지를 우선순위 큐에 저장하여 답을 구할 수 있다.

 

#include <bits/stdc++.h>
using namespace std;
typedef pair<long long, pair<int, int>> plii;
const long long INF = 0x3f3f3f3f3f3f3f3fLL;

struct cmp {
	bool operator() (plii A, plii B) {
		return A.first > B.first;
	}
};

int N, M, K;
long long ans = INF;
vector <pair<int, long long>> graph[10001];
long long dist[10001][21];

void Dijkstra(int start);

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> N >> M >> K;
	for (int i = 0; i < M; i++) {
		int A, B;
		long long C;
		cin >> A >> B >> C;
		graph[A].push_back({ B,C });
		graph[B].push_back({ A,C });
	}
	Dijkstra(1);
	for (int i = 0; i <= K; i++) ans = min(ans, dist[N][i]);
	cout << ans;
	return 0;
}

void Dijkstra(int start) {
	for (int i = 1; i <= N; i++) {
		for (int j = 0; j <= K; j++) dist[i][j] = INF;
	}
	priority_queue<plii, vector<plii>, cmp> pq;
	pq.push({ 0,{start, 0}});
	dist[start][0] = 0;
	while (pq.size()) {
		int now = pq.top().second.first;
		int num = pq.top().second.second;
		long long val = pq.top().first;
		pq.pop();
		if (dist[now][num] < val) continue;
		for (int i = 0; i < graph[now].size(); i++) {
			int next = graph[now][i].first;
			long long new_val = val + graph[now][i].second;
			if (dist[next][num] > new_val) {
				dist[next][num] = new_val;
				pq.push({ new_val, {next,num} });
			}
			if (num < K && dist[next][num + 1] > val) { // 도로를 포장하는 경우
				dist[next][num + 1] = val;
				pq.push({ val, {next, num + 1} });
			}
		}
	}
}