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

www.acmicpc.net/problem/1162

1162번: 도로포장

 

 

 

알고리즘 종류

다익스트라

DP

 

 

 

사고 과정

1번 노드에서 N번 노드로 가는 최소비용을 구하는 문제입니다. 이때, 도로를 포장하거나 하지 않을 수 있습니다. 접근하기 전에 가장 일반적인 다익스트라 문제를 생각해 보겠습니다.

 

이 문제를 기본적인 다익스트라 문제로 바꿔본다면, 모든 도로를 포장하지 않고 1번 노드에서 N번 노드로 이동하는 최소 비용을 구하는 문제가 될 것입니다. 그러면 모든 도로의 비용을 고려합니다.

 

이 문제는 도로를 포장하는 경우가 추가되었습니다. 그렇다면, 포장하는 경우를 고려할 수 있도록 2차원 배열을 만들겠습니다. costs[i][k]로 만들어서 1번 노드에서 j까지 k포장 횟수로 가는 최소 비용이라고 합시다. k는 최대값을 넘지 않도록 다익스트라를 구현하면 됩니다.

 

 

 

구현(C++)

#include <iostream>
#include <vector>
#include <queue>
#define INF 1e15
 
using namespace std;
 
typedef long long ll;
 
int n, m, k;
ll ans = INF;
 
ll costs[10001][21]; // 1번 노드에서 j 노드로 k번 포장해서 가는 최소 비용  
vector<vector<pair<int, int> > > edges;
 
 
void dijkstra(){
    
    // 초기화  
    for(int i=1; i<=n; i++){
        for(int j=0; j<=k; j++){
            costs[i][j] = INF;
        }
    }
    
    priority_queue<pair<ll, pair<int, int> > > pq; // cost, node, cnt
    pq.push({0, {1, 0}});
    costs[1][0] = 0;
    
    while(!pq.empty()){
        int node = pq.top().second.first;
        int cnt = pq.top().second.second;
        ll cost = -pq.top().first;
        pq.pop();
        
        if(costs[node][cnt] < cost) continue;
        
        for(int i=0; i<edges[node].size(); i++){
            int next_node = edges[node][i].first;
            ll next_cost = cost + edges[node][i].second;
            
            // 포장하지 않는 경우  
            if(costs[next_node][cnt] > next_cost){
                costs[next_node][cnt] = next_cost;
                pq.push({-next_cost, {next_node, cnt}});
            }
            
            // 포장할 경우  
            if(costs[next_node][cnt+1] > cost && cnt+1 <= k){
                costs[next_node][cnt+1] = cost;
                pq.push({-cost, {next_node, cnt+1}});
            }
        }
    }
}
 
 
int main(void){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
    cin >> n >> m >> k;
    
    edges.resize(n+1);
    
    int a, b, c;
    for(int i=0; i<m; i++){
        cin >> a >> b >> c;
        edges[a].push_back({b,c});
        edges[b].push_back({a,c});
    }
    
    dijkstra();
    
    for(int i=0; i<=k; i++) ans = min(ans, costs[n][i]);
    cout << ans << endl;
}

 

 

 

시행착오