[leetcode] 787.Kストップ内の最安フライト
787 Cheapest Flights Within K Stops
説明
m便で結ばれた都市はn都市あります。各戦いは都市uから始まり、価格wでvに到達します。
これで、すべての都市とフライトが、開始都市srcと目的地dstとともに与えられたので、あなたのタスクは、最大kストップでsrcからdstまでの最も安い価格を見つけることです。そのようなルートがない場合は、-1を出力します。
Example 1: Input: n = 3, edges = [[0,1,100],[1,2,100],[0,2,500]] src = 0, dst = 2, k = 1 Output: 200 Explanation: The graph looks like this:
The cheapest price from city 0 to city 2 with at most 1 stop costs 200, as marked red in the picture.
Example 2: Input: n = 3, edges = [[0,1,100],[1,2,100],[0,2,500]] src = 0, dst = 2, k = 0 Output: 500 Explanation: The graph looks like this:
The cheapest price from city 0 to city 2 with at most 0 stop costs 500, as marked blue in the picture.
注意:
- ノードの数nは[1、100]の範囲にあり、ノードには0からn-1のラベルが付けられます。
- フライトのサイズは[0、n *(n-1)/ 2]の範囲になります。
- 各フライトの形式は(src、dst、price)になります。
- 各フライトの価格は[1、10000]の範囲になります。
- kは[0、n-1]の範囲です。
- 重複したフライトやセルフサイクルはありません。
分析
タイトルの意味は次のとおりです。nの都市、mのフライトがあり、uからvに出発し、k回の通過後にuからvの最低価格を見つけます。
- ここでは、2次元のDP配列を使用します。ここで、dp [i] [j]はj位置へのi便のほとんどのフライトの最小価格を表し、dp [0] [src]は、の価格のために0に初期化されます。 0フライト両方が0で、K回転送します。実際、K + 1フライトを飛行すると、dp [i] [src]が0に初期化されるたびに、iが1からK + 1にトラバースを開始します。これは、開始点も0の場合、すべてのフライトxを通過する場合でも、dp [i] [x [1]]を更新します。これは、フライトiに到着するフライトiの目的地の最低価格を示し、最も多くのフライトiを使用します。 1便、到着便x出発地の価格にフライトxの価格を加えたもので、小さい方を更新できます。
コード
class Solution { public: int findCheapestPrice(int n, vector& flights, int src, int dst, int K) { vector dp(K+2,vector(n,1e9)) dp[0][src]=0 for(int i=1i=1e9) ? -1:dp[K+1][dst] } }
参照
[LeetCode] K内の最も安いフライトがKトランジット内の最も安いフライトを停止します