题目大意：
给定一个有向图，从u → v 有一条长度为w 的边
问从s 到t 的路径中，最多经过k 次中转的最短路径是多少？
思路：
首先看到题目意思之后，很难不往图论中的最短路去想，然后仔细一想就会发现用图论中的知识维护经过中转的次数顺便求得最短路会稍微有点困难，刚开始用弗洛伊德（动态规划思想）来解决，然后仔细一想，看过数据范围 k 的大小并且已知起点和终点，我们可以考虑使用动态规划的方法来解决
首先我们要明确一点：经过k 次中转则意味着要搭乘k + 1 次车，所以说我们定义 dp 转移式如下：
假设 u→to wight=w, dis[u][to]=w
dp[i][to]=min(dp[i][to],do[i−1][u]+w)
dp[i][to] 定义为第i 次搭乘车辆，从给定的 src 点到 to 的最小花费
其中，dp[0][src]=0 初始化要注意
Code:
class Solution { public: int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int k) { int dp[k+2][n]; memset(dp,0x3f3f3f3f,sizeof dp); dp[0][src] = 0; for(int i=1;i<=k+1;i++) for(vector<int> v: flights) { int u = v[0],to = v[1],w = v[2]; dp[i][to] = min(dp[i][to],dp[i-1][u]+w);// dp[i-1][u] } int ret = 0x3f3f3f3f; for(int i=1;i<=k+1;i++) { ret = min(ret,dp[i][dst]); } if(ret == 0x3f3f3f3f) return -1; return ret; } };
文章知识点与官方知识档案匹配，可进一步学习相关知识
算法技能树leetcode-动态规划22-括号生成8345 人正在系统学习中
