백준 1162번 도로포장 - C++ 풀이

---

 

1. 다익스트라를 이용하여 1번 정점부터 N번 정점까지의 최소 거리를 구한다.
2. 다익스트라의 dist 배열을 포장 횟수까지 포함하여 운영한다.
3. 다익스트라 과정에서 간선을 포장하지 않는 경우와 포장하는 경우를 모두 고려한다.

 

1. 다익스트라를 이용하여 1번 정점부터 N번 정점까지의 최소 거리를 구한다.

 두 정점의 최소 거리를 구하기 위해 다익스트라 알고리즘을 사용할 것이다.

 

2. 다익스트라의 dist 배열을 포장 횟수까지 포함하여 운영한다.

 중간에 최대 K개의 간선의 가중치를 0으로 만들 수 있으므로, dist 배열을 포장 횟수까지 고려하여 2차원으로 운영한다. dist[idx][k] = 포장을 k번해서 1번 정점에서 idx번 정점으로 가는 최소 시간으로 정의할 수 있다.

 

3. 다익스트라 과정에서 간선을 포장하지 않는 경우와 포장하는 경우를 모두 고려한다.

 일반적인 다익스트라 알고리즘에 간선을 포장하여 해당 간선의 가중치를 0으로 만들어 지나가는 경우까지 고려해주어야 한다. 현재까지의 포장 횟수가 K번 미만이라면, 더 포장할 수 있으므로 해당 간선을 포장하는 케이스까지 고려한다.

반응형

---

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

using namespace std;

typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<ll, pll> plll;
const ll INF = LLONG_MAX;

int N, M, K;
vector<pll> adjs[10001];

ll dijkstra() {
    // dist[idx][k]: k개의 포장을 했을 때, 1번노드에서 idx번 노드까지 최소 시간
    vector<vector<ll>> dist(10001, vector<ll>(21, INF));
    priority_queue<plll, vector<plll>, greater<plll>> pq; 
    
    dist[1][0] = 0;
    pq.push({0, {1, 0}});
    
    while (!pq.empty()) {
        ll d = pq.top().first;
        ll curr = pq.top().second.first;
        ll k = pq.top().second.second;
        pq.pop();
        
        if (d > dist[curr][k]) continue;
        
        for (int i=0; i<adjs[curr].size(); i++) {
            ll next = adjs[curr][i].first;
            ll w = adjs[curr][i].second;
            
            // 포장 안하는 경우
            if (d+w < dist[next][k]) {
                dist[next][k] = d+w;
                pq.push({d+w, {next, k}});   
            }
            
            // 포장하는 경우
            if (k < K && d < dist[next][k+1]) {
                dist[next][k+1] = d;
                pq.push({d, {next, k+1}});
            }
        }
    }
    
    return *min_element(dist[N].begin(), dist[N].end());
}

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++) {
        ll s, e, w;
        cin >> s >> e >> w;
        
        adjs[s].push_back({e, w});
        adjs[e].push_back({s, w});
    }
    
    cout << dijkstra();

    return 0;
}