Cheapest Flights Within K Stops

很久没有发文了，虽然还是有写题的习惯，但写解题真的有点懒(误

总而言之，最后还是决定写一下，毕竟要改掉这个坏习惯XD

题目连结

解题

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];    }};