<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>

typedef tuple<int,int,int> ti;
class Solution {
public:
    int findCheapestPrice( int n, vector<vector<int>>& flights, int src, int dst, int K ) { 
        unordered_map<int, vector<int>> graph;
        unordered_map<int,unordered_map<int, int>> p;
        vector<int> cost(n, INT_MAX);

        for (auto f: flights) {
            graph[f[0]].push_back(f[1]);
            p[f[0]][f[1]] = f[2];
        }

        queue<int> q;
        q.push(src);
        cost[src] = 0;
        int k = K + 1;
        while (k--) {
            int qn = q.size();
            vector<int> tmpCost = cost;
            while (qn--) {
                int cur = q.front();
                q.pop();

                for (auto nxt : graph[cur]) {
                    if (cost[cur] + p[cur][nxt] < tmpCost[nxt]) {
                        tmpCost[nxt] = cost[cur] + p[cur][nxt];
                        q.push(nxt);
                    }
                }
            }
            cost = tmpCost;
        }

        for (auto c : cost) {
            cout << c << ", ";
        }
        cout << endl;

        return cost[dst] == INT_MAX ? -1 : cost[dst];
    }









    // Solution1: BFS - TLE
    int findCheapestPrice6( 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;
    }
    
    // Solution2 - bellman-ford
    /*  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),
    */
    int findCheapestPrice1(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];
    }
    
    // Solution3 - Dijkstra - TLE
    /* 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)
    */
    int findCheapestPrice2(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, K+1 } ); // cost, vertex, hops
        
        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;

            if( stop > 0 )
                for( auto next : adjList[curr] )
                    minHeap.push( { cost+next.second, next.first, stop-1 } );
        }
        return -1;
    }
    
    // Solution4: DFS - TLE
    int findCheapestPrice3(int n, vector<vector<int>>& flights, int s, int d, int K) {
       unordered_map<int, vector<pair<int,int>>> g;
       for (const auto& e : flights)
            g[e[0]].emplace_back(e[1], e[2]);        
        int ans = INT_MAX;
        vector<int> visited(n,0);
        dfs(s, d, K + 1, 0, visited, ans, g);
        return ans == INT_MAX ? - 1 : ans;
    }
    
    void dfs(int s, int d, int k, int cost, vector<int>& visited, int& ans, unordered_map<int, vector<pair<int,int>>>& g ) {
        if (s == d) { ans = cost; return; }
        if (k == 0) return; 
        visited[s] = 1;
        for (const auto& x : g[s]) {
            if (visited[x.first] == 0) {
                if (cost + x.second > ans) continue; // IMPORTANT!!! prunning 
     
                dfs(x.first, d, k - 1, cost + x.second, visited, ans, g); 
             
            }
        }
        visited[s] = 0;
  }
    
    // Solution4: bellman ford.
    //just run it k+1 iterations.
    int findCheapestPrice4(int n, vector<vector<int>>& a, int src, int dst, int k) {
        vector<int> c(n, 1e8);
        c[src] = 0;
        
        for(int z = 0; z <= k; z++){
            vector<int> C(c);
            for (auto e : a)
                C[e[1]] = min(C[e[1]], c[e[0]] + e[2]);
            c = C;
        }
        return c[dst] == 1e8 ? -1 : c[dst];
    }
    
    // Solution5: Dijkstra's algorithm - TLE
    int findCheapestPrice5(int n, vector<vector<int>>& flights, int src, int dst, int K) {
        vector<vector<pair<int,int>>> vp(n);
        for(const auto& f : flights)   
            vp[f[0]].emplace_back(f[1],f[2]);
        
        // min heap
        priority_queue<ti, vector<ti>, greater<ti>> pq;
        pq.emplace(0, src, K+1);
        while(!pq.empty()){
            auto [cost, u, stops] = pq.top();
            pq.pop();
            if (u == dst)  return cost;
            if (!stops)  continue;
            for (auto to : vp[u]){
                auto [v,w] = to;
                pq.emplace(cost+w, v, stops-1);
            }
        }
        return -1;
    }
};
18825