787_CheapesTFlightKStop_DijktrasAlgo.cpp

#include<unordered_map>
#include<queue>

using namespace std;

typedef tuple <int, int, int> tupl;
long findCheapestPrice(int cities, vector<vector<int>>& flights, int src, int dst, int stops)
{
	//adjList
	vector<vector<pair<int, int>>> adjList(cities);
	for (auto flight : flights)
	{
		adjList[flight[0]].push_back({ flight[1], flight[2] });
	}

	//min queue
	priority_queue<tupl, vector<tupl>, greater<tupl>>pq;
	pq.push({ 0, src, stops });

	while (!pq.empty())
	{
		tupl t = pq.top();
		pq.pop();

		if (src == dst) return 0;

		int cost = get<0>(t);
		int current = get<1>(t);
		int stop = get<2>(t);

		if (current == dst)
			return cost;

		if (stop >= 0)
		{
			for (auto next : adjList[current])
			{
				pq.push({(cost + next.second), next.first, stop - 1 });
			}
		}
	}
	return -1;
}

int mainD()
{
	//input flight : {Source, Destination, Cost}
	vector<vector<int>> flights = { {4,1,1 }, { 1, 2, 3 }, { 0, 3, 2 }, { 0, 4, 10 }, { 3, 1, 1 }, { 1, 4, 3 } };

	//vec, n, stops, src , dst
	int stops = 2;
	int totalCities = 5;
	int sourceCity = 0;
	int destCity = 4;
	long ans = findCheapestPrice(totalCities, flights, sourceCity, destCity, stops);
	return 0;
}