[BaekJoon][1162] 도로포장

BAEKJOON ONLINE JUDGE

1162 도로포장

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

다익스트라 + DP

평소 다익스트라는 그냥 그래프의 개수만큼 정점을 탐색하는데,

이 visit 정점 배열을 DP 배열로 놓고, DP[도시 개수][포장 가능 도로의 수]로 놓고 풀면 된다.

다익스트라 구현 시 반복문 안에는 다른 도시로 영역을 넓힐 때 포장가능 할 때 포장하는 경우와 포장을 하지 않는 경우 둘 다 queue에 넣어주어 구현하면 된다.

#include <cstdio>
#include <vector>
#include <queue>
using namespace std;
 
typedef long long LL;
 
#define INF    1e15
#define Min(x, y)        (((x) < (y)) ? (x) : (y))
 
int n, m, k;
vector<pair<int, int> >city[10001];
LL dp[10001][21];
 
void init() {
    for (int i = 0; i <= n; i++) {
        for (int j = 0; j <= k; j++) {
            dp[i][j] = INF;
        }
    }
}
 
void dijkstra()
{
    priority_queue<pair<LL, pair<int, int> > > que;
    
    que.push(make_pair(0, make_pair(1, k)));
    dp[1][k] = 0;
 
    while (!que.empty()) {
 
        int current = que.top().second.first;
        int cnt = que.top().second.second;
        LL w = que.top().first * -1;
        que.pop();
 
        if (dp[current][cnt] <= w) {
            for (int i = 0; i < city[current].size(); i++) {
                int next = city[current][i].first;
                LL cost = city[current][i].second + w;
 
                if (cnt > 0 && w < dp[next][cnt - 1]) {    // 포장할 수 있는 수가 더 있으면
                    dp[next][cnt - 1] = w;
                    que.push(make_pair(w * -1, make_pair(next, cnt - 1)));
                }
 
                if (cost < dp[next][cnt]) {
                    dp[next][cnt] = cost;
                    que.push(make_pair(cost * -1, make_pair(next, cnt)));
                }
            }
        }
    }
}
 
int main()
{
    int from, to, w;
 
    scanf("%d %d %d", &n, &m, &k);
 
    init();
 
    for (int i = 0; i < m; i++) {
        scanf("%d %d %d", &from, &to, &w);
        city[from].push_back(make_pair(to, w));
        city[to].push_back(make_pair(from, w));
    }
 
    dijkstra();
 
    LL ans = INF;
 
    for (int i = 0; i <= k; i++) {
        ans = Min(ans, dp[n][i]);
    }
    
    printf("%lld\n", ans);
 
    return 0;
}

이해는 했는데 다시 풀라고 하면 한번에는 못맞을 듯...