文章目錄

• • 1. 題目
  • 2. 解題

1. 題目

有 n 個(gè)城市通過(guò) m 個(gè)航班連接。每個(gè)航班都從城市 u 開(kāi)始，以價(jià)格 w 抵達(dá) v。

現(xiàn)在給定所有的城市和航班，以及出發(fā)城市 src 和目的地 dst，你的任務(wù)是找到從 src 到 dst 最多經(jīng)過(guò) k 站中轉(zhuǎn)的最便宜的價(jià)格。
如果沒(méi)有這樣的路線，則輸出 -1。

示例 1：

輸入: n = 3, edges = [[0,1,100],[1,2,100],[0,2,500]] src = 0, dst = 2, k = 1 輸出: 200 從城市 0 到城市 2 在 1 站中轉(zhuǎn)以內(nèi)的最便宜價(jià)格是 200，如圖中紅色所示。

示例 2：

輸入: n = 3, edges = [[0,1,100],[1,2,100],[0,2,500]] src = 0, dst = 2, k = 0 輸出: 500 解釋: 城市航班圖如下 從城市 0 到城市 2 在 0 站中轉(zhuǎn)以內(nèi)的最便宜價(jià)格是 500，如圖中藍(lán)色所示。

提示： n 范圍是 [1, 100]，城市標(biāo)簽從 0 到 n - 1. 航班數(shù)量范圍是 [0, n * (n - 1) / 2]. 每個(gè)航班的格式 (src, dst, price). 每個(gè)航班的價(jià)格范圍是 [1, 10000]. k 范圍是 [0, n - 1]. 航班沒(méi)有重復(fù)，且不存在環(huán)路

來(lái)源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/cheapest-flights-within-k-stops
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處。

2. 解題

參考：圖Graph–最短路徑算法（Shortest Path Algorithm）

typedef pair<int,pair<int,int>> piii; struct cmp{bool operator()(piii& a, piii& b) const{return a.first > b.first;//價(jià)格低的優(yōu)先} }; 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;//在某點(diǎn)，走了幾步的最少花費(fèi)priority_queue<piii,vector<piii>,cmp> q;q.push({0, {src, 0}});//路徑機(jī)票價(jià)格總和, 當(dāng)前點(diǎn)，走了幾步int id, money, ntid, cost, step;while(!q.empty()){money = q.top().first;//之前總的花費(fèi)id = q.top().second.first;//當(dāng)前點(diǎn)step = q.top().second.second;//到這走了幾步if(id == dst)//找到目標(biāo)return price[id][step];q.pop();for(auto it = g[id].begin(); it != g[id].end(); ++it){ntid = it->first;//下一個(gè)點(diǎn)cost = it->second;//需要的花費(fèi)if(step+1 <= K && money+cost < price[ntid][step+1]){ //步數(shù)還可以走 && 花費(fèi)較小price[ntid][step+1] = money+cost;q.push({money+cost, {ntid, step+1}});}}}return -1;} };

40 ms 12.2 MB

---

我的CSDN博客地址 https://michael.blog.csdn.net/

長(zhǎng)按或掃碼關(guān)注我的公眾號(hào)（Michael阿明），一起加油、一起學(xué)習(xí)進(jìn)步！

創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎(jiǎng)勵(lì)來(lái)咯，堅(jiān)持創(chuàng)作打卡瓜分現(xiàn)金大獎(jiǎng)

總結(jié)

以上是生活随笔為你收集整理的LeetCode 787. K 站中转内最便宜的航班（Dijkstra最短路径 + 优先队列）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。