1162번

1162번 - 도로 포장

다익스트라를 이용해서 문제를 풀었다. 그런데 어떤 점을 큐에 넣을 때 판단해야 할 점이 하나 더 있었다.

포장한 도로이지 아닌지 여부를 파악해줘야 했다. 다행히 저번에 BFS를 3차원배열을 이용해서 풀었던 문제와 비슷했다.

차원을 하나 더 추가하면서 풀 수 있게 됐다.

기본적인 로직은 다익스트라로, 그 다음 dist 배열에 오면서 몇번이나 포장했는지 여부를 저장하면서 문제를 풀었다.

####

점을 방문했을 때의 상태를 한 차원 더 표현하면 문제가 쉬워질 수 있다.

<정답 코드>

#include<iostream>
#include<vector>
#include<queue>
using namespace std;
 
const int INF = 987654321;
int main()
{
    //freopen("input.txt", "r", stdin);
    int n, m, k;
    cin >> n >> m >> k;
    vector<vector<pair<int, int>>> v(n + 1);
    while (m--)
    {
        int from, to, w;
        cin >> from >> to >> w;
        v[from].push_back({ to,w });
        v[to].push_back({ from,w });
    }
 
    int start = 1, dest = n;
    vector<vector<int>> dist(n + 1, vector<int>(k+1,INF) );
    dist[start][0] = 0;
    priority_queue<pair<pair<int, int>, int>> q;
    q.push({ { 0 ,start },0 });
 
    while (!q.empty())
    {
        int here = q.top().first.second;;
        int cost = -q.top().first.first;
        int used = q.top().second;
        q.pop();
 
        if (cost > dist[here][used])
        {
            continue;
        }
 
        for (int i = 0; i < v[here].size(); i++)
        {
            int there = v[here][i].first;
            int w = v[here][i].second;
            int t_use = used;
 
            if (t_use < k)
            {
                if (dist[there][t_use + 1] > cost)
                {
                    dist[there][t_use + 1] = cost;
                    q.push({ { -dist[there][t_use + 1],there },t_use + 1 });
                }
            }
            if (dist[there][t_use] > cost + w)
            {
                dist[there][t_use] = cost + w;
                q.push({ {-dist[there][t_use],there},t_use });
            }
        }
    }
 
    int minn = INF;
    for (int i = 0; i <= k; i++)
    {
        if (dist[n][i] < INF)
        {
            minn = dist[n][i];
        }
    }
 
    cout << minn << endl;
 
    return 0;
}