<p>There are <code>n</code> cities connected by some number of flights. You are given an array <code>flights</code> where <code>flights[i] = [from<sub>i</sub>, to<sub>i</sub>, price<sub>i</sub>]</code> indicates that there is a flight from city <code>from<sub>i</sub></code> to city <code>to<sub>i</sub></code> with cost <code>price<sub>i</sub></code>.</p>

<p>You are also given three integers <code>src</code>, <code>dst</code>, and <code>k</code>, return <em><strong>the cheapest price</strong> from </em><code>src</code><em> to </em><code>dst</code><em> with at most </em><code>k</code><em> stops. </em>If there is no such route, return<em> </em><code>-1</code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2022/03/18/cheapest-flights-within-k-stops-3drawio.png" style="width: 332px; height: 392px;" />
<pre>
<strong>Input:</strong> n = 4, flights = [[0,1,100],[1,2,100],[2,0,100],[1,3,600],[2,3,200]], src = 0, dst = 3, k = 1
<strong>Output:</strong> 700
<strong>Explanation:</strong>
The graph is shown above.
The optimal path with at most 1 stop from city 0 to 3 is marked in red and has cost 100 + 600 = 700.
Note that the path through cities [0,1,2,3] is cheaper but is invalid because it uses 2 stops.
</pre>

<p><strong class="example">Example 2:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2022/03/18/cheapest-flights-within-k-stops-1drawio.png" style="width: 332px; height: 242px;" />
<pre>
<strong>Input:</strong> n = 3, flights = [[0,1,100],[1,2,100],[0,2,500]], src = 0, dst = 2, k = 1
<strong>Output:</strong> 200
<strong>Explanation:</strong>
The graph is shown above.
The optimal path with at most 1 stop from city 0 to 2 is marked in red and has cost 100 + 100 = 200.
</pre>

<p><strong class="example">Example 3:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2022/03/18/cheapest-flights-within-k-stops-2drawio.png" style="width: 332px; height: 242px;" />
<pre>
<strong>Input:</strong> n = 3, flights = [[0,1,100],[1,2,100],[0,2,500]], src = 0, dst = 2, k = 0
<strong>Output:</strong> 500
<strong>Explanation:</strong>
The graph is shown above.
The optimal path with no stops from city 0 to 2 is marked in red and has cost 500.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= n &lt;= 100</code></li>
	<li><code>0 &lt;= flights.length &lt;= (n * (n - 1) / 2)</code></li>
	<li><code>flights[i].length == 3</code></li>
	<li><code>0 &lt;= from<sub>i</sub>, to<sub>i</sub> &lt; n</code></li>
	<li><code>from<sub>i</sub> != to<sub>i</sub></code></li>
	<li><code>1 &lt;= price<sub>i</sub> &lt;= 10<sup>4</sup></code></li>
	<li>There will not be any multiple flights between two cities.</li>
	<li><code>0 &lt;= src, dst, k &lt; n</code></li>
	<li><code>src != dst</code></li>
</ul>


// class Solution {
// //BFS

// O(E*K), 
// public:
// int findCheapestPrice( int n, vector<vector<int>>& flights, int src, int dst, int K ) { 
// 	// Create adjList
// 	unordered_map<int, vector< pair<int,int> > > adjList;
// 	for( auto flight : flights )
// 		adjList[flight[0]].push_back( { flight[1], flight[2] } );

// 	/* BFS starting from src */
// 	queue< pair<int,int> > q; // < node, dist_from_src > pair
// 	q.push( { src, 0 } ); 
// 	int srcToTgtDist = INT_MAX; // result

// 	while( !q.empty() && K-- >= 0 ) {
// 		int size = q.size();
// 		for( int i = 0; i < size; i++ ) {
// 			auto curr = q.front(); q.pop();         
// 			for( auto nbr : adjList[curr.first] ) {
// 				if( srcToTgtDist < curr.second + nbr.second ) continue;

// 				q.push( { nbr.first, curr.second + nbr.second } );

// 				// update distance from src to dst
// 				if( dst == nbr.first ) 
// 					srcToTgtDist = min( srcToTgtDist, curr.second + nbr.second );
// 				}
// 		}
// 	}
// 	return srcToTgtDist == INT_MAX ? -1 : srcToTgtDist;
// }
// };

// class Solution {
//     public:
// //Bellman-Ford Algorithm
//     /*  In bellman-ford algo calculates the shortest distance from the source
//         point to all of the vertices.
//         Time complexity of Bellman-Ford is O(VE),

//          O(K*E) , space = O(V)
//     */
//     int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int K) {
//         /* distance from source to all other nodes */
//         vector<int> dist( n, INT_MAX );
//         dist[src] = 0;
        
//         // Run only K+1 times since we want shortest distance in K hops
//         for( int i=0; i <= K; i++ ) {
//             vector<int> tmp( dist );
//             for( auto flight : flights ) {
//                 if( dist[ flight[0] ] != INT_MAX ) {
//                     tmp[ flight[1] ] = min( tmp[flight[1]], dist[ flight[0] ] + flight[2] );
//                 }
//             }
//             dist = tmp;
//         }
//         return dist[dst] == INT_MAX ? -1 : dist[dst];
//     }
    
// };


class Solution {
    public:
//Dijkstra Algo
    /* Dijkstra’s Algorithm allows you to calculate the shortest path between 
    one node of your choosing and every other node in a graph. 
    
    Given a graph and a source vertex in the graph, find shortest paths from source
    to all vertices in the given graph.
    
    We generate a SPT (shortest path tree) with given source as root. We maintain
    two sets, one set contains vertices included in shortest path tree, other set
    includes vertices not yet included in shortest path tree. At every step of the
    algorithm, we find a vertex which is in the other set (set of not yet included)
    and has a minimum distance from the source.
    
    Time Complexity:  If we take a closer look, we can observe that the statements
    in inner loop are executed O(V+E) times (similar to BFS).
    So overall time complexity is O(E+V)*O(LogV) which is O((E+V)*LogV) = O(ELogV)
    
    O(V^2⋅log V),
    space = O(V^2)
    */

    int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int K) {
          // create adjacency list
        unordered_map<int,vector<pair<int, int>>> adjList;
        for( auto f : flights )
            adjList[f[0]].push_back( { f[1], f[2] } );
        
        // minHeap based on cost of distance from source
        priority_queue< vector<int>, vector<vector<int>>, greater<vector<int>> > minHeap;
        minHeap.push( { 0, src, 0 } ); // cost, vertex, hops
        
        vector<int> dist(n+1, INT_MAX); //to avoid TLE
        
        while( !minHeap.empty() ) {
            auto t = minHeap.top(); minHeap.pop();
            int cost = t[0];
            int curr = t[1];
            int stop = t[2];
            
            if( curr == dst )
                return cost;
            
                //Optimization to avoid TLE
            if(dist[curr]<stop) continue;
                 dist[curr]=stop;

            if(stop >K ) continue;
            
                for( auto next : adjList[curr] )
                    minHeap.push( { cost+next.second, next.first, stop+1 });
        }
        return -1;
    }
};




// DFS: O(n^k)
// BFS: O(n^k)
// BF: O(m*k)
// PQ: O(n^k * k * log(n^k))
// 
// sPACE
// DFS: O(m + k) (we need to store the graph)
// BFS: O(m*k) (a tuple for each relaxed edge)
// BF: O(n) (two cost arrays)
// Dijkstra: O(m + n^k) (graph + PQ)

// To show that these are upper bounds, we can say that:
// for DFS/BFS at each vertex we have at most k branches;
// for BF, each edge is relaxed at most k times (once for each step);
// for PQ, the queue can grow in size up to n ^ k, and each PQ query takes time O(log(size of PQ)) = O(log(n ^ k)) = O(k * log n).
19485