Cheapest Flights Within K Stops

很久沒有發文了，雖然還是有寫題的習慣，但寫解題真的有點懶(誤

總而言之，最後還是決定寫一下，畢竟要改掉這個壞習慣XD

題目連結

解題

• 難度: 中等
• 需要基本bfs觀念

board紀錄從起點該點花費
用陣列(vector)qp紀錄這是第幾層，如果遇到重複路徑就找花費最小(前提是符合限制步數，替換原board紀錄花費)
用road確定下一步(下一層)，將點與花費推入qp

總結

這題基本上就是要找花費最小到達目的地的費用，但有步數的限制，所以用Dijkstra演算法會很麻煩，所以就直接bfs硬幹就玩了(欠揍

#define 原神 啟動

class Solution {
public:
    int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int k) {
        //拜訪花費
        vector<int>board(n+1,INT_MAX);
        //路線 || from || to || cost
        map<int,vector<pair<int,int>>> road;
        //填充路線&價錢
        for(const auto it : flights){
            road[it[0]].push_back({it[1],it[2]});
        }
        //
        queue<pair<int,int>> qp;
        //初始化出發點與花費
        qp.push({src,0});

        while(k>=0){
            // 經典BFS走法
            int size = qp.size();
            while(size--){
                // 這一步的花費
                int curr_cost = qp.front().second;
                for(auto it:road[qp.front().first]){
                    // 往前走的花費
                    int new_cost = it.second+curr_cost;
                    int next_step = it.first;
                    if(new_cost<board[next_step]){
                        board[next_step] = new_cost;
                        qp.push({next_step,new_cost});
                    }
                }
                qp.pop();
            }
            k--;
        }
        return board[dst]==INT_MAX?-1:board[dst];
    }
};