K站中转内最便宜的航班

题目链接：https://leetcode-cn.com/problems/cheapest-flights-within-k-stops
题目描述：
有 n 个城市通过一些航班连接。给你一个数组 flights ，其中 flights[i] = [fromi, toi, pricei] ，表示该航班都从城市 fromi 开始，以价格 pricei 抵达 toi。
现在给定所有的城市和航班，以及出发城市 src 和目的地 dst，你的任务是找到出一条最多经过 k 站中转的路线，使得从 src 到 dst 的 价格最便宜 ，并返回该价格。 如果不存在这样的路线，则输出 -1。

题解：

题解链接LeetCode K站中转内最便宜的航班（回溯法、动态规划）
回溯法：

class Solution {
public:
    int minCost = INT_MAX;
    int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int k) {
        vector<vector<int>> graph(n, vector<int>(n, -1));
        for(auto &flight : flights)    //构建图信息
            graph[flight[0]][flight[1]] = flight[2];
        vector<bool> visited(n, false);     //标记数组
        visited[src] = true;
        trackingBack(graph, visited, n, dst, k, 0, src, 0);
        return minCost == INT_MAX ? -1 : minCost;
        
    }

    void trackingBack(vector<vector<int>> &graph, vector<bool> visited, int n, int dst, int k, int haveCost, int nowSrc, int myK)
    {
        if(nowSrc == dst)  //得到一种方案
        {
            minCost = min(minCost, haveCost);
            return;
        }
            
        //剪枝：中转个数超过了k，花费超过了当前已找到的最小花费
        if(myK > k || haveCost >= minCost)
            return;
        //遍历节点
        for(int i = 0; i < n; i++)
        {
            if(!visited[i] && graph[nowSrc][i] != -1)
            {
                visited[i] = true;
                trackingBack(graph, visited, n, dst, k, haveCost + graph[nowSrc][i], i, myK + 1);
                visited[i] = false;
            }
        }

    }
    
};