LeetCode#787

LeetCode#787K站中转内最便宜的航班

题目链接
果然万物都可dp…才知道原来这种图题也可以用dp做。
题意大概就是：给你一个数组，里面包含起始站和终点站以及花费的加钱，然后给个起始站，给个终点站，再给个k表示从起始站到终点站最多能经历几次换站，问最少需要花费多少钱，不能到达则输出-1。
如果用二维dp的话还是比较好理解的，因为规定了起始站，所以第一维表示起始站到达的站，第二维表示经过了多少中转站。状态转移方程就是：

dp[dst][k] = min(dp[dst][k],dp[dst][k-1],dp[src][k-1]+val) //第三个表示上一个点到当前这个点

初始化的时候要注意不要越界，其他就是一些简单的细节啦：

class Solution {
public:
    int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int K) {
        vector<vector<long> >dp(n+1,vector<long>(K+1,INT_MAX));//因为INT_MAX,所以变成long类型的了
        for(auto flight : flights)//先进行初始化
            if(flight[0] == src)
                dp[flight[1]][0] = flight[2];

        for(int i = 1 ; i <= K ; i++)//从0开始的话会越界，因为已经初始化过直接不经中转到的情况了所以直接k从1开始就行了
            for(auto flight : flights)
                {
                    int s = flight[0];
                    int e = flight[1];
                    int v = flight[2];
                    dp[e][i] = min(dp[e][i],min(dp[e][i-1],dp[s][i-1]+v));
                }
        if(dp[dst][K] == INT_MAX)
            return -1;
        return dp[dst][K];
    }
};