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

✏️ 문제 링크

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

1162번: 도로포장

 

 

✏️ 문제 설명 (더보기 클릭 👆🏻)

 

✏️ 문제 풀이

1. 도로와 비용 배열

이전에는 dist배열이 1차원으로 시작노드에서 모든 노드까지의 최소 경로를 구하는 방식이었다. 하지만 이번 문제에서는 1번노드에서 다른 노드로 가는데! 몇번 포장을 해서 가냐, 또 k번 포장해서 해당 노드를 갔을 때의 최소비용이 무엇인지 알 필요가 있다. 따라서 ll dist[MAX][21]에 저장되는 정보는 1번째 노드에서 각 i번째로 k번 포장해서 가는 최소 비용을 의미한다. 예를 들어 dist[2][1]에은 1번째 노드에서 2번째 노드로 도로를 1번 포장해서 가는 최소 비용을 저장할것이다. 

vector<pii> vec[MAX];
ll dist[MAX][21];

 

2. 두 가지 경우

이제 priority_queue에 push할 때 두 가지 경우가 있다! 다음 도로를 포장할 것이냐! 아니면 그 비용 그대로 가지고 갈 것이냐! 두가지를 모두 고려하여 pq에 넣어준다. 

//도로를 포장하지 않는 경우
if(nxt_c<dist[nxt][k]){
   dist[nxt][k]=nxt_c;
   pq.push({-nxt_c, {nxt, k}});
}
            
//도로를 포장하는 경우
if(cost<dist[nxt][k+1] && k+1<=K){
   dist[nxt][k+1]=cost;
   pq.push({-cost, {nxt, k+1}});
}

 

3. 최소비용

처음에는 그냥 dist[N][K]를 구했는데... 문제에서 k이하의 도로를 포장한 경우!라고 나와있기 때문에 아래와 같이 N번째 노드로 k번 포장하는 경우 모두 중 최소값을 구해줘야된다. 

ll ans=INF;
for(int i=0; i<=K; i++) ans=min(ans, dist[N][i]);

 

 

✏️ 문제 코드

#include <bits/stdc++.h>

using namespace std;
using pii=pair<int, int>;

#define MAX 10001
#define INF 1e15

typedef long long ll;
vector<pii> vec[MAX];
ll dist[MAX][21];

int N, M, K;

void dijkstra(){
    
    priority_queue<pair<ll, pii>> pq; pq.push({0, {1, 0}});//cost, node, k
    dist[1][0]=0;
    
    while(!pq.empty()){
        pair<ll, pii> t=pq.top(); pq.pop();
        int node=t.second.first;
        int k=t.second.second;
        ll cost=-t.first;
        
        if(dist[node][k]<cost)continue;
        
        for(int i=0; i<vec[node].size(); i++){
            int nxt=vec[node][i].first;
            ll nxt_c=vec[node][i].second + cost;
            
            if(nxt_c<dist[nxt][k]){
                dist[nxt][k]=nxt_c;
                pq.push({-nxt_c, {nxt, k}});
            }
            
            if(cost<dist[nxt][k+1] && k+1<=K){
                dist[nxt][k+1]=cost;
                pq.push({-cost, {nxt, k+1}});
            }
        }
    }
    
}
int main(){
    cin>>N>>M>>K;
    
    //input
    while(M--){
        int a, b, c; cin>>a>>b>>c;
        vec[a].push_back({b, c});
        vec[b].push_back({a, c});
    }
    
    //set 
    for(int i=1; i<=N; i++)
        for(int j=0; j<=K; j++)
           dist[i][j]=INF;
    
    dijkstra();
    
    ll ans=INF;
    for(int i=0; i<=K; i++) ans=min(ans, dist[N][i]);
    
    cout<<ans;
    return 0;
}

 

 

 

 ⭐ if feedback and question : comment please⭐