Leetcode787: K站中转内最便宜的航班

有 n 个城市通过 m 个航班连接。每个航班都从城市 u 开始，以价格 w 抵达 v。

现在给定所有的城市和航班，以及出发城市 src 和目的地 dst，你的任务是找到从 src 到 dst 最多经过 k 站中转的最便宜的价格。 如果没有这样的路线，则输出 -1。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/cheapest-flights-within-k-stops
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

【重点】
使用unorder_map 记录adjacent list
unordered_map<int, vector<pair<int,int>>> adjacent_map
前面的int是出发地，后面的pair中第一个是到达地，第二个是cost。可能会有很多组这种数据，所以map中后面的数据类型用vector 可以添加多个邻近的node

也是使用unorder_map 记录到达地的cost和times
unordered_map<int, unordered_map<int, int>> desPrice;
int 到达地，times对应的cost只有一个，所以后一个用map

用prirotiy queue维护优先队列，需要重写比较函数，具体写法见代码

struct cmpFun{
    bool operator()(vector<int> & a, vector<int> &b){
        return a[1] > b[1];
    }
};


int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int K) {
//Leetcode787: K站中转中最便宜的票价
    unordered_map<int, vector<pair<int,int>>> adjacent_map;
    unordered_map<int, unordered_map<int, int>> desPrice;
    for(int i = 0; i < flights.size();i++)
    {   //construct adjacent map
        adjacent_map[flights[i][0]].push_back({flights[i][1],flights[i][2]});
        
    }
    
    //construct distance map
    priority_queue<vector<int>, vector<vector<int>>, cmpFun> disQueue;
    for(int i = 0; i < n;i++){
        for(int j = 0; j <= K;j++)
        desPrice[i][j] = INT32_MAX;
    }
    
    disQueue.push({src,0,-1});
    // node 0 的初始times应该是-1 因为没有飞 这样子它的邻近城市的times会被更新成0  which is 更加合理
    while(!disQueue.empty()){
        vector<int> curFlight = disQueue.top();
        disQueue.pop();
        int des = curFlight[0];
        int cost = curFlight[1];
        int times = curFlight[2];
        
        cout<<"des: "<<des<<" cost: "<<cost<<" times: "<<times<<endl;
        
        if(times  > K || cost > desPrice[des][times]){
//如果times比K大那么不符合要求 舍弃  如果这个cost比它本来的price还要大 也舍弃
            cout<<desPrice[des][times]<<endl;
            cout<<"larger than k times"<<endl;
            continue;
        }
        
        if(des == dst) return cost;  //pick 到了
        
        desPrice[des][times] = min(cost, desPrice[des][times]); //更新
        vector<pair<int,int>> adjList = adjacent_map[des];
        for(int i = 0; i < adjList.size();i++){
            disQueue.push({adjList[i].first,cost + adjList[i].second,times + 1}); //不管是几个times都会加入
        }
    }
    
    cout<<"desPrice"<<endl;
    
    return -1;
    
}