Minimum cost path from source node to destination node via K intermediate nodes

#include <bits/stdc++.h>

using namespace std;

  

int leastWeightedSumPath(int n,

                         vector<vector<int> >& edges,

                         int src, int dst, int K)

{

    

    unordered_map<int,

                  vector<pair<int, int> > >

        graph;

  

    

    for (vector<int>& edge : edges) {

        graph[edge[0]].push_back(

            make_pair(edge[1], edge[2]));

    }

  

    

    priority_queue<vector<int>, vector<vector<int> >,

                   greater<vector<int> > >

        pq;

  

    

    

    

    vector<vector<int> > costs(n,

                               vector<int>(

                                   K + 2, INT_MAX));

  

    costs[src][K + 1] = 0;

  

    

    

    

    pq.push({ 0, src, K + 1 });

  

    while (!pq.empty()) {

        

        

        auto top = pq.top();

  

        pq.pop();

  

        

        if (top[1] == dst)

  

            

            return top[0];

  

        

        if (top[2] == 0)

            continue;

  

        

        for (auto neighbor : graph[top[1]]) {

  

            

            if (costs[neighbor.first][top[2] - 1]

                < neighbor.second + top[0]) {

                continue;

            }

  

            

            costs[neighbor.first][top[2] - 1]

                = neighbor.second + top[0];

  

            

            pq.push({ neighbor.second + top[0],

                      neighbor.first, top[2] - 1 });

        }

    }

  

    

    return -1;

}

  

int main()

{

    int n = 3, src = 0, dst = 2, k = 1;

    vector<vector<int> > edges

        = { { 0, 1, 100 },

            { 1, 2, 100 },

            { 0, 2, 500 } };

  

    

    

    

    cout << leastWeightedSumPath(n, edges,

                                 src, dst, k);

  

    return 0;

}

Let's block ads! (Why?)