백준 1162:도로포장

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

백준 1162번 도로포장 문제에요! 각 지점에서 도로를 몇번포장했는지 각각 다 체크해주어야하기 때문에 visited배열을 [정점수][포장사용한횟수]로 만들어줘야해요. 마지막에는 visited[정점수]에서 최솟값을 찾아주면 됩니다. *paved를 사용하면 paved++, 그냥이동(비용0) 사용하지않으면 기존의 다익스트라 알고리즘사용.

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
 
#define endl '\n'
#define INF (static_cast<int>(1e9))
typedef pair<int, int> PAIR;
 
int d(vector<vector<PAIR>>& graph, const int& K) {
    const int N = graph.size();
    priority_queue<pair<int,PAIR>> pq;
    vector<vector<int>> visited(N, vector<int>(K + 1, INF));
    //방문 안한것은 INF로 초기화
    
    //pair<비용, pair<정점, 포장횟수>> 를 사용했어요
    pq.push(pair<int, PAIR>(-0, PAIR(0, 0)));
    visited[0][0] = 0;//시작은 포장안한 0번 정점
 
    while (!pq.empty()) {//다익스트라 알고리즘
        int cur, paved;
        do {//현재 정점과 포장횟수까지필요해요
            cur = pq.top().second.first;
            paved = pq.top().second.second;
            pq.pop();
        } while (!pq.empty() && visited[cur][paved] == INF);
        if (visited[cur][paved] == INF) break;
 
        for (auto& i : graph[cur]) {
            int next = i.first, distance = i.second;
            if (paved < K && visited[next][paved + 1] > visited[cur][paved]) {
                visited[next][paved + 1] = visited[cur][paved];
                pq.push(pair<int, PAIR>(-visited[next][paved + 1], PAIR(next, paved + 1)));
            }//1조건 : paved를 다 사용하지 않은경우 도로포장해서 비용 0으로 이동
            if (visited[next][paved] > visited[cur][paved] + distance) {
                visited[next][paved] = visited[cur][paved] + distance;
                pq.push(pair<int, PAIR>(-visited[next][paved], PAIR(next, paved)));
            }//2조건 : paved를 다썼다면.. 비용지불하고 이동ㅠㅠ
        }
    }
 
    int minimum = INF;
    for (const auto& i : visited[N - 1]) {
        minimum = min(minimum, i);
    }//마지막점에서 최솟값을 찾아요
 
    return minimum;
}
 
int main(void) {
    ios::sync_with_stdio(false);
    int N, M, K; cin >> N >> M >> K;
    
    vector<vector<PAIR>> graph(N);
 
    for (int i = 0; i < M; i++) {
        int u, v, c; cin >> u >> v >> c;
        graph[u - 1].push_back(PAIR(v - 1, c));
        graph[v - 1].push_back(PAIR(u - 1, c));
    }
 
    int ans = d(graph, K);
    cout << ans << endl;
 
 
    return 0;
}