[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:

フライト2



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トランジット内の最も安いフライトを停止します