[백준/C++] 1162번 도로포장

백준

---

🤔문제 이해

1번 정점에서 N번 정점까지 가는 모든 경로 중에 최대 k개의 도로 이동 시간이 0이 되었을 때 시간이 가장 적게 드는 경로의 시간을 구하는 문제이다.

---

💡첫번째 아이디어

다익스트라 문제이지만 도로를 포장해야 한다는 점에서 더 어려웠다. 스터디 멘토님이 가르쳐준 방법은 아래 풀이와 같다.

 

🔥풀이🔥

최단경로 문제에서 최단거리를 저장하는 1차원 배열을 2차원 배열로 바꾸어 dist[i][j]에서 j는 도로를 포장한 횟수를 의미한다.

따라서 다익스트라로 구현하되 j값이 문제에서 주어지는 포장가능한 도로의 개수 k보다 작을 때 도로를 한 번 포장한 값을 j+1에 넣어주고 포장하지 않았을 때의 값을 j에 업데이트 해준다.

정점 n에 도착하면 break해주고 나서는 도로를 몇번 포장했을 때 가장 최소인지를 비교해서 최솟값을 찾아준다. (k를 다 쓰지 않고도 최솟값일 수 있음)

 

❌트러블 슈팅

값의 범위를 제대로 확인하지 않아 값이 제대로 담기지 않았음

---

#include <iostream>
#include <vector>
#include <queue>
#include <cmath>

#define INF 90000000000
using namespace std;

int n, m, k;
long long dist[10002][21];
vector<vector<pair<int, int>>> edge;

int main() {
    cin.tie(nullptr);
    cout.tie(nullptr);
    ios::sync_with_stdio(false);

    cin >> n >> m >> k;
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= k; j++) {
            dist[i][j] = INF;
        }
    }
    int a, b, c;
    edge.resize(n + 1);

    for (int i = 0; i < m; i++) {
        cin >> a >> b >> c;
        edge[a].push_back({b, c});
        edge[b].push_back({a, c});
    }
    priority_queue<pair<long long, pair<int, int>>> pq; //거리, 정점, 포장개수
    pq.push({0, {1, 0}});

    while (!pq.empty()) {
        long long weight = -pq.top().first;
        int vertex = pq.top().second.first;
        int packed = pq.top().second.second;
        pq.pop();
        if (vertex == n) break;
        if (weight > dist[vertex][packed]) continue;

        for (auto e: edge[vertex]) {
            int next = e.first;
            long long cost;
            if (packed < k) {
                cost = 0;
                if (dist[next][packed + 1] > weight + cost) {
                    dist[next][packed + 1] = weight + cost;
                    pq.push({-(weight + cost), {next, packed + 1}});
                }
            }
            cost = e.second;
            if (dist[next][packed] > weight + cost) {
                dist[next][packed] = weight + cost;
                pq.push({-(weight + cost), {next, packed}});
            }
        }
    }
    long long min_cost = INF;
    for (int i = 0; i <= k; i++) {
        if (min_cost > dist[n][i]) min_cost = dist[n][i];
    }
    cout << min_cost;
}

 

🔗참고할 문제

[백준/C++] 1753번 최단경로