[Dijkstra]BOJ 1162_도로 포장

문제 링크 : www.acmicpc.net/problem/1162

1162번: 도로포장

어떠한 도시에 도착했을 때, 몇 개의 도로를 포장해서 이동했는지는 구별되어야 한다.

이전 포스팅인 BOJ16118_달빛 여우 문제처럼 가중치에 어떤 요소가 더해졌을 때는

이를 구별하기 위해 DP를 섞어 사용한다.

따라서, dist 배열을 dist[n][k]와 같은 이차원 배열 형태로 구성해 문제를 해결하자.

dist[i][j] = i번 도시에 j개의 도로를 포장하여 도착했을 때의 최소비용

 

이런 유형의 문제들은 정점을 확장시킨다는 개념으로 접근하면 쉽게 해결할 수 있다.

기존의 n개 도시에 대한, 즉 n개의 노드가 존재하는 그래프에서의 다익스트라에서

각 노드마다 최대 k+1개의 구별되는 상태가 있으므로,

(k+1)n 개의 노드가 존재하는 그래프에 대한 다익스트라로 이해하면 된다.

 

[코드]

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <queue>
 
#define INF 9999999999999
 
using namespace std;
typedef pair<long long, int> p;
 
int n, m, k;
long long dist[10001][21];
vector<p> adj[10001];
 
void dijkstra() {
    //시간, 포장 갯수, 노드
    priority_queue<pair<p, int>> pque;
    pque.push({ { 0, 0 }, 1});
    dist[1][0] = 0;
 
    while (!pque.empty()) {
        pair<p, int> cur = pque.top();
        pque.pop();
 
        long long distval = -cur.first.first;
        int roads = cur.first.second;
        int node = cur.second;
 
        if (node == n) continue;
 
        if (dist[node][roads] >= distval) {
            for (int i = 0; i < adj[node].size(); i++) {
                int nextnode = adj[node][i].first;
                long long newDist = distval + adj[node][i].second;
                //포장하지 않고 지나갈 경우
                if (dist[nextnode][roads] > newDist) {
                    dist[nextnode][roads] = newDist;
                    pque.push({ { -newDist, roads }, nextnode });
                }
                //포장하고 지나갈 경우
                if (roads < k && dist[nextnode][roads + 1] > distval) {
                    dist[nextnode][roads + 1] = distval;
                    pque.push({ { -distval, roads + 1 }, nextnode });
                }
            }
        }
    }
}
 
void init() {
    int f, s, w;
    cin >> n >> m >> k;
 
    for (int i = 0; i < m; i++) {
        cin >> f >> s >> w;
        adj[f].push_back({ s, w });
        adj[s].push_back({ f, w });
    }
 
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= k; j++) {
            dist[i][j] = INF;
        }
    }
}
 
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(NULL);
 
    init();
    dijkstra();
 
    long long answer = INF;
    for (int i = 0; i <= k; i++) {
        answer = min(answer, dist[n][i]);
    }
 
    printf("%lld\n", answer);
 
    return 0;
}