Самые дешевые рейсы в пределах K Stops - PullRequest
Новая
       60

Самые дешевые рейсы в пределах K Stops

0 голосов
/ 21 ноября 2018

так что я видел много решений этой проблемы.вот ссылка на полную проблему https://leetcode.com/problems/cheapest-flights-within-k-stops/description/.

Он запрашивает самый дешевый путь от src до dest с K остановками.большинство решений используют для этого Беллмана Форда (слегка модифицированного с k + 1 итерациями).Единственный способ заставить BF работать, это изменить его, как я нашел во многих онлайн-решениях, используя вектор хранения TEMP (см. Ниже).вектор temp_dp (dp) смущает меня ... То, что я видел из алгоритма BFs, это то, что вы ослабляете ребро U-> V и меняете V в векторе расстояния.здесь они меняют его во временном векторе и переназначают его (что заставляет его работать), любой может объяснить, как это работает. 

int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int K) {
    vector<int> dp(n, INT_MAX);
    dp[src] = 0;
    for(int z = 0; z <= K; z++){
    vector<int> temp_dp(dp);
        for(auto e: flights) {
            if (dp[e[0]] < INT_MAX) {
                temp_dp[e[1]] = min(temp_dp[e[1]], dp[e[0]] + e[2]);
            }
        } 
        dp = temp_dp;
    }
    return dp[dst] == INT_MAX ? -1 : dp[dst];
}
...