LeetCode 787. K 站中转内最便宜的航班（Dijkstra最短路径 + 优先队列）

输入: 
n = 3, edges = [[0,1,100],[1,2,100],[0,2,500]]
src = 0, dst = 2, k = 1
输出: 200
从城市 0 到城市 2 在 1 站中转以内的最便宜价格是 200，如图中红色所示。

输入: 
n = 3, edges = [[0,1,100],[1,2,100],[0,2,500]]
src = 0, dst = 2, k = 0
输出: 500
解释: 
城市航班图如下
从城市 0 到城市 2 在 0 站中转以内的最便宜价格是 500，如图中蓝色所示。

提示：
n 范围是 [1, 100]，城市标签从 0 到 n - 1.
航班数量范围是 [0, n * (n - 1) / 2].
每个航班的格式 (src, dst, price).
每个航班的价格范围是 [1, 10000].
k 范围是 [0, n - 1].
航班没有重复，且不存在环路

typedef pair<int,pair<int,int>> piii;
struct cmp{
    bool operator()(piii& a, piii& b) const
    {
        return a.first > b.first;//价格低的优先
    }
};
class Solution {
public:
    int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int K) {
        vector<unordered_map<int,int>> g(n);
        for(auto& f : flights)
        {
            g[f[0]][f[1]] = f[2];
        }
        K++;//可以走K+1步
        vector<vector<int>> price(n, vector<int>(K+1,INT_MAX));
        price[src][0] = 0;//在某点，走了几步的最少花费
        priority_queue<piii,vector<piii>,cmp> q;
        q.push({0, {src, 0}});//路径机票价格总和, 当前点，走了几步
        int id, money, ntid, cost, step;
        while(!q.empty())
        {
            money = q.top().first;//之前总的花费
            id = q.top().second.first;//当前点
            step = q.top().second.second;//到这走了几步
            if(id == dst)//找到目标
                return price[id][step];
            q.pop();
            for(auto it = g[id].begin(); it != g[id].end(); ++it)
            {
                ntid = it->first;//下一个点
                cost = it->second;//需要的花费
                if(step+1 <= K && money+cost < price[ntid][step+1])
                {   //步数还可以走 && 花费较小
                    price[ntid][step+1] = money+cost;
                    q.push({money+cost, {ntid, step+1}});
                }
            }
        }
        return -1;
    }
};