백준 1162 - 도로포장(C++)

문제 링크입니다. https://www.acmicpc.net/problem/1162

1162번: 도로포장

DP와 다익스트라 알고리즘을 사용하는 문제입니다.

N의 값이 10000이하이기에 다익스트라를 구현하면 시간 초과가 걸립니다.

따라서 DP의 개념을 이용해 다익스트라를 구현해야 합니다.

 

먼저 도로 개통을 할 수 있기에 X번 도시를 도착한 경우를 나눠줘야합니다.

즉 X번 도시를 도착했을 때, 도로를 몇번 개통했는지에 따라 다르게 계산해야 된다는 의미입니다.

따라서 비용의 최솟값을 저장하는 Distance 배열을 1차원이 아닌, 2차원 배열로 설정해 X번 도시 + 도로 개통 횟수로 저장해줍니다.

 

다익스트라를 구현하는 방법입니다.

1. X번 도로를 도착했을 때, 현재 도시의 비용이 Distance의 값보다 큰지 확인합니다.

   -> 크다면 해당 경우에서 탐색을 할 필요가 없습니다.

2. 도로 포장의 횟수가 K보다 작을 경우, 도로 포장을 한 경우를 확인합니다.

3. 도로 포장을 하지 않는 경우를 확인합니다.

  -> 2번과 3번은 같이 이뤄줘야합니다. 2번이 실행되었다고 3번이 실행 안되는 것이 아닌, 같이 실행되야합니다.

 

마지막으로 N번 도시에서의 Distance의 최솟값을 구합니다.

 

 

자세한 것은 코드를 참고해주세요

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <vector>
#include <queue>
#include <cmath>
#include <cstdio>
#define INF 21000000000000
#define pp pair<long long , pair<int,int>>
using namespace std;

int N, M, K;
vector<pair<int,int>> connect[10001]; 
priority_queue<pp> q;
long long Distance[10001][21];

void reset_distance(){
	for(int i = 1; i <= N; i++){
		for(int j = 0; j <= K; j++){
			Distance[i][j] = INF;
		}
	}
}

void dp_Dijstra(int start){
	Distance[start][0] = 0;
	q.push({-Distance[start][0],{start,0}});
	while(!q.empty()){
		int x = q.top().second.first;
		int pave = q.top().second.second;
		long long  cost = -q.top().first;
		q.pop();
		if(cost > Distance[x][pave]) continue;
		for(int i = 0; i < connect[x].size(); i++){
			int xx = connect[x][i].first;
			int dis = connect[x][i].second;			
            if(pave < K){
				if(Distance[xx][pave+1] > cost){
					Distance[xx][pave+1] = cost;
					q.push({-Distance[xx][pave+1],{xx,pave+1}});
				}	
			}
			if(Distance[xx][pave] > cost + dis){
				Distance[xx][pave] = cost + dis;
				q.push({-Distance[xx][pave],{xx,pave}});
			}
		}
	}		
}

void solve(){
	reset_distance();
	dp_Dijstra(1);
	long long mini = INF;
	for(int i = 0; i <= K; i++){
		mini = min(mini, Distance[N][i]);
	}
	cout << mini;
}

int main(){
	cin.tie(0);
	cout.tie(0);
	cin >> N >> M >> K;
	for(int i = 0; i < M; i++){
		int x, y, cost;
		cin >> x >> y >> cost;
		connect[x].push_back({y,cost});
		connect[y].push_back({x,cost});
	}
	solve();
	return 0;
}

 

 

질문 및 조언 댓글 남겨주세요