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

문제

준영이는 매일 서울에서 포천까지 출퇴근을 한다. 하지만 잠이 많은 준영이는 늦잠을 자 포천에 늦게 도착하기 일쑤다. 돈이 많은 준영이는 고민 끝에 K개의 도로를 포장하여 서울에서 포천까지 가는 시간을 단축하려 한다.

문제는 N개의 도시가 주어지고 그 사이 도로와 이 도로를 통과할 때 걸리는 시간이 주어졌을 때 최소 시간이 걸리도록 하는 K개의 이하의 도로를 포장하는 것이다. 도로는 이미 있는 도로만 포장할 수 있고, 포장하게 되면 도로를 지나는데 걸리는 시간이 0이 된다. 또한 편의상 서울은 1번 도시, 포천은 N번 도시라 하고 1번에서 N번까지 항상 갈 수 있는 데이터만 주어진다.

입력

첫 줄에는 도시의 수 N(1 ≤ N ≤ 10,000)과 도로의 수 M(1 ≤ M ≤ 50,000)과 포장할 도로의 수 K(1 ≤ K ≤ 20)가 공백으로 구분되어 주어진다. M개의 줄에 대해 도로가 연결하는 두 도시와 도로를 통과하는데 걸리는 시간이 주어진다. 도로들은 양방향 도로이며, 걸리는 시간은 1,000,000보다 작거나 같은 자연수이다.

출력

첫 줄에 K개 이하의 도로를 포장하여 얻을 수 있는 최소 시간을 출력한다.

예제 입출력

• 예제 입력 1

4 4 1
1 2 10
2 4 10
1 3 1
3 4 100

• 예제 출력 1

1

Solution

#include <iostream>
#include <queue>
#include <vector>
#define INF 1e15
#define MAX 10001
#define ll long long
using namespace std;

vector<pair<int, int>> edge[MAX];
ll Dist[MAX][21];

void Dijkstra(int K){
    priority_queue<pair<ll, pair<int, int>>> PQ;
    PQ.push({0, {1, 0}});
    Dist[1][0] = 0;
    while(!PQ.empty()){
        int Current = PQ.top().second.first;
        int count = PQ.top().second.second;
        ll cost = -PQ.top().first;
        PQ.pop();
        if(Dist[Current][count] < cost) continue;
        for(int i = 0; i < edge[Current].size(); i++){
            int next = edge[Current][i].first;
            ll nCost = edge[Current][i].second + cost;
            if(Dist[next][count] > nCost){
                Dist[next][count] = nCost;
                PQ.push({-nCost, {next, count}});
            }
            if(Dist[next][count+1] > cost && count+1 <= K){
                Dist[next][count+1] = cost;
                PQ.push({-cost, {next, count+1}});
            }
        }
    }
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    ll answer = INF;
    int N, M, K; cin >> N >> M >> K;
    for(int i = 0 ; i < M; i++){
        int src, dst, cost;
        cin >> src >> dst >> cost;
        edge[src].push_back({dst, cost});
        edge[dst].push_back({src, cost});
    }
    for(int i = 0; i < MAX; i++) fill_n(Dist[i], 21, INF);
    Dijkstra(K);
    for(int i = 0; i <= K; i++) answer = min(answer, Dist[N][i]);
    cout << answer << '\n';
}

다익스트라 응용문제. 상당히 고생을 많이 했던 문제다.

기존의 다익스트라와는 다르게 한 가지 조건이 존재한다. 포장.
포장을 하게 된다면 기존의 Cost를 그대로 사용해서 해당 경로로 이동할 수 있다.
뻔한 main함수는 제외하고 바로 다익스트라 코드를 보자.

#include <iostream>
#include <queue>
#include <vector>
#define INF 1e15
#define MAX 10001
#define ll long long
using namespace std;

vector<pair<int, int>> edge[MAX];
ll Dist[MAX][21];

void Dijkstra(int K){
    priority_queue<pair<ll, pair<int, int>>> PQ;
    PQ.push({0, {1, 0}});
    Dist[1][0] = 0;
    while(!PQ.empty()){
        int Current = PQ.top().second.first;
        int count = PQ.top().second.second;
        ll cost = -PQ.top().first;
        PQ.pop();
        if(Dist[Current][count] < cost) continue;
        for(int i = 0; i < edge[Current].size(); i++){
            int next = edge[Current][i].first;
            ll nCost = edge[Current][i].second + cost;
            if(Dist[next][count] > nCost){
                Dist[next][count] = nCost;
                PQ.push({-nCost, {next, count}});
            }
            if(Dist[next][count+1] > cost && count+1 <= K){
                Dist[next][count+1] = cost;
                PQ.push({-cost, {next, count+1}});
            }
        }
    }
}

Priority Queue에 적제되는 데이터의 순서는 비용, 현재 위치, 포장 횟수다.
일반적인 다익스트라 문제라면 그냥 무조건 다음 edge로 가는 비용을 토대로 다음 비용을 책정했겠지만 포장을 하게 된다면 해당 edge의 비용을 무시 할 수 있다.

즉 K번 포장을 할 수 있으니까 매 탐색마다 두 가지를 계산한다.
1. 기존의 다익스트라 처럼 지금 이 경로를 이동하는 게 더 비용이 적게 드는가?
2. 만약 포장을 한다면 포장 하는 게 비용이 더 적게 드는가?

for(int i = 0; i <= K; i++) answer = min(answer, Dist[N][i]);
cout << answer << '\n';

최종적으로 Dist에는 기존 다익스트라와는 다르게 K개의 데이터가 저장 되어있다. 하나도 포장하지 않고 가는 것과 i번 ~ K번 포장 한 데이터. 이 중에서 최솟값을 가져오면 된다.