[BOJ/백준] 1162번 - 도로포장

문제 링크

• http://icpc.me/1162

문제 출처

• USACO February 2009 Contest > Gold 3번

사용 알고리즘

• 다익스트라

풀이

특정 노드에서 목표 지점까지의 최소 시간을 구해야 하기에, 다익스트라를 사용하면 됩니다.

다만, K개 이하의 도로를 포장할 수 있기 때문에, 이를 해결하기 위한 전략이 필요합니다.

최소 거리를 구하는 배열에 포장한 횟수를 포함해줍시다.

dist[N][K] => K개를 포장했을 때, N노드에서의 최소 거리

• 처음 문제를 접했을 때, 위상 정렬처럼 보였지만 DAG가 아니므로 사용하지 못합니다.
• 최악의 경우, N의 최댓값(1e5) * 걸리는 시간의 최댓값(1e6), 즉 100억이 되므로, int가 아닌 long long을 사용해야 합니다.

전체 코드

#include<bits/stdc++.h>
using namespace std;

#define INF 1e15
#define ll long long

const int mxN=1e4+1, mxK=21;
int n, m, k;
vector<pair<int, int>> arr[mxN];
ll dist[mxN][21];

void solve() {
    priority_queue<pair<ll, pair<int, int>>> q;
    dist[1][0] = 0;
    q.push({dist[1][0], {0, 1}});

    while(!q.empty()) {
        ll cost = -q.top().first;
        int now = q.top().second.second;
        int cnt = q.top().second.first;
        q.pop();

        if(dist[now][cnt] < cost) continue;

        for(int i=0; i<arr[now].size(); i++) {
            int next = arr[now][i].first;
            ll nextcost = arr[now][i].second;

            if(dist[next][cnt] > dist[now][cnt] + nextcost) {
                dist[next][cnt] = dist[now][cnt] + nextcost;
                q.push({-dist[next][cnt], {cnt, next}});
            }
        if(cnt < k) {           
            if(dist[next][cnt+1] > dist[now][cnt]) {
                dist[next][cnt+1] = dist[now][cnt];
                q.push({-dist[next][cnt+1], {cnt+1, next}});
            }        
        }   
    }
}
}


int main() {
    ios_base :: sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    cin >> n >> m >> k;
    for(int i=0; i<m; i++) {
        int fr, to, val; cin >> fr >> to >> val;
        arr[fr].push_back({to, val});
        arr[to].push_back({fr, val});
    }

    for(int i=2; i<=n; i++) {
        for(int j=0; j<=k; j++) {
            dist[i][j] = INF;
        }
    }

    solve();
    ll ans = INF;
    for(int i=0; i<=k; i++) {
        ans = min(dist[n][i], ans);
    }
    cout << ans;
}