BOJ 1162 도로포장

백준 1162 도로포장 링크

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

1162번: 도로포장

문제풀이

dp[지금도시위치][도로 포장한 회수] 배열을 만들어 비교하였습니다.

 

큐에서 꺼낼때 지금 갈 도로가 포장을 할 수 있는가 (포장한 회수 + 1 <= 최대 포장 수)를 확인한 뒤에 그렇다면 포장을 한 상태로 큐에 넣고, 또 포장하지 않고 지나가는 경우도 고려하여 큐에 넣습니다.

 

dp와 완전탐색이 섞인 문제같네요

코드

#include<iostream>
#include<vector>
#include<queue>
using namespace std;
typedef struct {
    long long cost;
    int now, left_pave;

}edge;
bool operator <(edge a, edge b) {
    return a.cost > b.cost;
}
int n, m, k;
priority_queue <edge> q;
vector <pair<int, long long>> con[10003];
long long dp[10003][22];
void dajik() {
    q.push({ 0,1,0 });
    while (!q.empty()) {
        int now = q.top().now;
        int cnt = q.top().left_pave;
        long long cost = q.top().cost;
        q.pop();
        if (dp[now][cnt] != cost)
            continue;
        for (auto i : con[now]) {
            int next = i.first;
            if (cost < dp[next][cnt + 1] && cnt + 1 <= k) {
                dp[next][cnt + 1] = cost;
                q.push({ dp[next][cnt + 1], next, cnt + 1 });
            }
            if (dp[next][cnt] > cost + i.second) {
                dp[next][cnt] = cost + i.second;
                q.push({ dp[next][cnt], next, cnt });
            }
        }
    }
}
int main() {
    freopen("input.txt", "r", stdin);
    cin >> n >> m >> k;
    while (m--) {
        int a, b, cost;
        cin >> a >> b >> cost;
        con[a].push_back({ b,cost });
        con[b].push_back({ a,cost });
    }
    for (int i = 0; i < 10003; i++) {
        for (int j = 0; j < 22; j++) {
            dp[i][j] = 1000000000000000;
        }
    }
    dp[1][0] = 0;

    dajik();
    long long min = 1000000000000000;
    for (int i = 0; i <= k; i++) {
        if (min > dp[n][i]) {
            min = dp[n][i];
        }
    }
    cout << min;
}