[백준] 1165 도로포장

방학에 못풀어서 넘어간 문제다

다익스트라로 풀면 되는데 K개의 도로를 포장한다는게 굉장히 걸린다

다익스트라를 돌리면서 dp를 사용하여 풀 수 있다.

d[here][cnt] 테이블을 잡고 here까지 오는데 cnt개의 도로를 포장했을 때로 생각하면 된다

기존 다익스트라 

+

만약 cnt<=k 일 때

d[next][cnt+1] > d[here][cnt] 라면 도로를 포장해준다

소스코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>
#include <queue>
using namespace std;
int n, m, k;
vector<vector<pair<int, int>>> Graph;
int d[10010][22];
bool check[10010][22];
 
int main() {
    
    scanf(" %d %d %d", &n, &m, &k);
    Graph.resize(n);
    for (int i = 0; i < m; i++) {
        int u, v, w; scanf(" %d %d %d", &u, &v, &w);
        u--; v--;
        Graph[u].push_back({ v,w });
        Graph[v].push_back({ u,w });
    }
    
    for (int i = 0; i <= n; i++) {
        for (int j = 0; j <= k; j++) {
            d[i][j] = 2e9;
        }
    }
    priority_queue<pair<int, pair<int, int>>> pq;
    d[0][0] = 0;
    pq.push({ 0,{0,0} });
    while (!pq.empty()) {
        int here = pq.top().second.first;
        int cost = -pq.top().first;
        int cnt = pq.top().second.second;
        pq.pop();
        
        if (check[here][cnt]) continue;
        check[here][cnt] = true;
 
        for (int i = 0; i < Graph[here].size(); i++) {
            int next = Graph[here][i].first;
            int ncost = -cost - Graph[here][i].second;
            if (d[next][cnt] > -ncost) {
                d[next][cnt] = -ncost;
                pq.push({ ncost,{next,cnt} });
            }
            if (cnt + 1 <= k && d[next][cnt + 1] > d[here][cnt]) {
                d[next][cnt + 1] = d[here][cnt];
                pq.push({ -cost,{next,cnt + 1} });
            }
        }
    }
 
    int ans = 2e9;
    for (int i = 0; i <= k; i++) {
        if (check[n - 1][i]) ans = min(ans, d[n - 1][i]);
    }
    printf("%d\n", ans);
}