[BOJ] 1162번: 도로포장

1162번: 도로포장

제한 조건
- 시간 제한 : 2s
- 공간 제한 : 128MB

풀이 사용 
- 사용 언어 : C++17
- 사용 시간 : 100ms
- 사용 공간 : 7068KB

풀이 설명
- 우선순위 큐를 이용한 다익스트라 순회를 하는 문제이다.
- 또한 포장 횟수를 구분하면서 최소비용을 계산해야하기 때문에 Dynamic Programming을 해야한다.
- DP[i][j] : 도로를 j번 포장하여 도시 i번에 도달하는 최소비용
- 위의 DP를 낮은 비용의 다익스트라 순회를 하면서 포장하는 혹은 포장하지 않는 경우를 계산하여 DP배열을 채워나가면 된다.
- 이후 DP[목적지][0~K] 중에서 가장 적은값을 출력해주면 된다.
- 이 문제도 비용을 long long형으로 해야 해결된다. 

#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
#include <cstring>

using namespace std;

#define FAST
#define MAX_CITYS 10001
#define MAX_PATHS 50001
#define MAX_PAVED 21
#define MAX_COST 1000001

typedef pair<long long, pair<int, int>> pp; // cost , u , v

struct comparator
{
    bool operator()(const pp &l, const pp &r) const
    {
        return l.first > r.first;
    }
};

int N_citys, M_edges, K_paves;                 // 도시개수, 도로개수, 포장가능개수
vector<pair<int, long long>> edges[MAX_CITYS]; // edges[i] : 도시i의 {도로, 비용} 리스트
long long dp[MAX_CITYS][MAX_PAVED];            // dp[i][j] : j번 포장하여 도시i에 도달하는 최소비용
priority_queue<pp, vector<pp>, comparator> pq; // 다익스트라용 우선순위큐. 계산할 가까운 도시를 찾는다.

int main(int argc, char const *argv[])
{

#pragma region 입력부

    scanf("%d %d %d\n", &N_citys, &M_edges, &K_paves);

    for (long long i = 0; i < M_edges; i++)
    {
        long long city1, city2;
        long long cost;
        scanf("%d %d %lld\n", &city1, &city2, &cost);
        edges[city1].push_back({city2, cost});
        edges[city2].push_back({city1, cost});
    }

#pragma endregion

#pragma region 다익스트라

    for (int i = 0; i < MAX_CITYS; i++)
        for (int j = 0; j < MAX_PAVED; j++)
            dp[i][j] = __INT64_MAX__;

    pq.push({0, {1, 0}});
    dp[1][0] = 0;

    while (!pq.empty())
    {
        long long cur_cos = pq.top().first;
        int cur_pos = pq.top().second.first;
        int cur_pav = pq.top().second.second;
        pq.pop();

        // 현재 기록보다 더 안좋은 경우라면 무시한다.
        if (dp[cur_pos][cur_pav] < cur_cos)
            continue;

        for (int i = 0; i < edges[cur_pos].size(); i++)
        {
            long long nxt_cos = cur_cos + edges[cur_pos][i].second;
            int nxt_pos = edges[cur_pos][i].first;

            // 포장하지 않고 나아지는 경우
            if (nxt_cos < dp[nxt_pos][cur_pav])
            {
                dp[nxt_pos][cur_pav] = nxt_cos;
                pq.push({nxt_cos, {nxt_pos, cur_pav}});
            }

            // 포장횟수가 남아있고, 포장하고 나아지는 경우
            if (cur_pav < K_paves && cur_cos < dp[nxt_pos][cur_pav + 1])
            {
                dp[nxt_pos][cur_pav + 1] = cur_cos;
                pq.push({cur_cos, {nxt_pos, cur_pav + 1}});
            }
        }
    }

#pragma endregion

#pragma region 최소값 출력부

    long long answer = dp[N_citys][0];
    for (int i = 1; i <= K_paves; i++)
        answer = min(answer, dp[N_citys][i]);
    printf("%lld", answer);

#pragma endregion

    return 0;
}