[BAE/<JOON> 문제풀이] 1162. 도로 포장

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

1162번: 도로포장

핵심::
Dijkstra 문제에 고려해야 하는 요소 k가 추가 되었으므로 거리 배열에 한 차원 추가하고 DP

풀이::
추가적으로 포장할 수 있는 횟수가 남아있다면 포장한 도로와 포장하지 않은 도로를 모두 우선순위 큐에 삽입한다.

또한 기존의 거리 배열에 남은 포장횟수를 고려하여 다음과 같이 변경한다.

distance[k][목적지] = 목적지까지 k번 도로 포장 했을 때 최소 거리

또한 기존 우선순위 큐를 사용하는 Dijkstra 알고리즘은 거리 저장배열을 -1로 초기화하고 이미 방문된 정점은

최소거리가 구해진것으로 판단하지만 이 문제에서는 특정한 간선의 거리를 0으로 만들 수 있기 떄문에 최댓값으로 초기화하고

구해진 거리가 기존 거리보다 짧을 때만 갱신하도록 작성했다. ( 이 부분은 어느게 더 정확한 풀이인지 모르겠음 )

의견::
다익스트라가 오랜만이라 헷갈림

코드::

#define _CRT_SECURE_NO_WARNINGS

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

using namespace std;

using ull = long long;

struct node {
    ull dest, dist, k;
};

struct cmp {
    bool operator () (node a, node b) {
        return a.dist > b.dist;
    }
};

bool cmpf(node a, node b) {
    return a.dist < b.dist;
}

int main()
{
    int n, m, k;
    cin >> n >> m >> k;
    vector<vector<node>> arr(n + 1);
    for (int i = 1; i <= m; i++) {
        int start, dist, dest;
        scanf("%d %d %d", &start, &dest, &dist);
        arr[start].push_back({ dest,dist });
        arr[dest].push_back({ start,dist });
    }

    priority_queue<node, vector<node>, cmp> pq;
    vector<vector<ull>> distance(k + 1, vector<ull>(n + 1, 9223372036854775807));
    for (int i = 0; i < k; i++) {
        distance[i][1] = 0;
    }
    pq.push({ 1, 0, 0 }); // 도시 번호, 거리, 포장한 도로 개수
    ull mx = 9223372036854775807;
    while (!pq.empty()) {
        const auto current = pq.top(); pq.pop();       

        if (distance[current.k][current.dest] < current.dist) continue;

        for (const auto nx : arr[current.dest]) {
            if (nx.dest == n) {
                if (current.k == k) {
                    mx = mx < (current.dist + nx.dist) ? mx : (current.dist + nx.dist);
                }
                else {
                    mx = mx < current.dist ? mx : current.dist;
                }
                continue;
            }
            if (current.k < k) {
                if (distance[current.k + 1][nx.dest] > current.dist) {
                    distance[current.k + 1][nx.dest] = current.dist;
                    pq.push({ nx.dest, current.dist, current.k + 1 });
                }
            }
            if (distance[current.k][nx.dest] > current.dist + nx.dist) {
                distance[current.k][nx.dest] = current.dist + nx.dist;
                pq.push({ nx.dest, current.dist + nx.dist, current.k });
            }
        }
    }

    cout << mx;
    return 0;
}