[c++] 백준 #1162 도로포장 (190903)

< 풀이 >

다익스트라 알고리즘에 DP를 곁들인듯한 그런 문제이다. 무시 가능한 남은 도로의 개수를 dp로 계산해줘야 한다. 

dp[a][k]는 a까지 가는데 무시 가능한 도로의 남은 개수가 k개 있을 때를 의미하는데,

다익스트라에서 현재 edge를 무시한 cost를 dp[a][k-1]에, 합한 cost를 dp[a][k]에 넣어주면 된다. 그 이후 dp[N][0]~dp[N][K]까지 min값을 취하면 된다. 이 때 cost 값이 int형을 넘어갈 수 있으니 long long의 max값인 9223372036854775807 ? 이라는 값으로 INF를 바꿔주어야 한다.

직접 생각한 풀이는 아닌데 해보니까 생각보다 어렵지는 않았던 문제이다. 

 

< 소스코드 >

#include <bits/stdc++.h>
using namespace std;
#define INF 9223372036854775807
#define mp make_pair
#define pb push_back
typedef long long ll;
typedef pair<int, int> ii;
typedef tuple<int, int, int> iii;

int N, M, K;
vector<pair<ll, ll> > adj[10010];


vector<vector<ll> > dijkstra(int src){
    priority_queue<pair<ll, pair<ll, ll> > > pq;
    vector<vector<ll> > dist(10010, vector<ll>(21, INF));

    dist[src][K] = 0;
    pq.push(mp(0, mp(src, K)));
    while(!pq.empty()){
        ll cost = -pq.top().first;
        ll here = pq.top().second.first;
        ll k = pq.top().second.second;
        pq.pop();
        if (dist[here][k] < cost) continue;

        for (int i = 0; i<adj[here].size();i++){
            ll there = adj[here][i].first;
            ll nextDist = cost + adj[here][i].second;

            if (dist[there][k] > nextDist){
                dist[there][k] = nextDist;
                pq.push(mp(-nextDist, mp(there, k)));
            }
            
            if (k > 0 && (dist[there][k-1] > cost)){
                dist[there][k-1] = cost;
                pq.push(mp(-cost, mp(there, k-1)));
            }
        }
    }
    return dist;
}


int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> N >> M >> K;
    ll a, b, val;
    for(int i=0; i<M;i++){
        cin >> a >> b >> val;
        adj[a].push_back(make_pair(b, val));
        adj[b].push_back(make_pair(a, val));
    }
    
    vector<vector<ll> > dist = dijkstra(1);
    
    ll min_time = INF;
    for(int i=0; i<K;i++){
        min_time = min(min_time, dist[N][i]);
    }

    cout << min_time << '\n';

    return 0;
}