<style>
html, body, .ui-content {
background: #222222;
color: #00BFFF;
}
/* 設定 code 模板 */
.markdown-body code,
.markdown-body tt {
background-color: #ffffff36;
}
.markdown-body .highlight pre,
.markdown-body pre {
color: #ddd;
background-color: #00000036;
}
.hljs-tag {
color: #ddd;
}
.token.operator {
background-color: transparent;
}
/* 設定連結 */
a,
.open-files-container li.selected a {
color: #89FFF8;

}
a:hover,
.open-files-container li.selected a:hover {
color: #89FFF890;
}

</style>

###### tags: `Leetcode`

# 787. Cheapest Flights Within K Stops

###### Link : https://leetcode.com/problems/cheapest-flights-within-k-stops/description/

## 題目
找到從src到dst的最短距離，並且最多只能經過k個點。
## 程式碼

class Solution {
public:
    int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int k) {
        //adj <int, vector<pair<int, int>>>
        //<目前的點, vector<pair<目前點可到的點，距離>>>
        unordered_map<int, vector<pair<int, int>>> adj;
        for(auto &it : flights){
            adj[it[0]].push_back({it[1], it[2]});
        }//按照adj格式放入(上方註解)
        vector<int> dis(n, -1);
        queue<pair<int, int>> Queue;
        //這一輪走到的點和權重
        Queue.push({src, 0});
        dis[src] = 0;
        k++;
        while(!Queue.empty()){
            if(!k) break;
            int size = Queue.size();
            //這次Queue須走幾遍，一次只走一步
            //以計算經過的停靠站
            for(int i = 0;i < size;i++){
                auto cur=Queue.front();
                Queue.pop();
                for(auto it : adj[cur.first]){
                   int len = cur.second + it.second;
                   if(dis[it.first]==-1||len<dis[it.first]){
                        dis[it.first]=len;
                        Queue.push({it.first, len});
                   }
                }
            }
            k--;
        }
        return dis[dst];
    }
};

## Date
### 2023/1/26