Untitled
unknown
plain_text
8 months ago
1.3 kB
0
Indexable
Never
class Solution { public: struct cmp { bool operator()(const pair<int,pair<int,int>>& a, const pair<int,pair<int,int>>& b) { return a.second.first > b.second.first; } }; int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int K) { vector<vector<pair<int,int>>> adj(n); for(auto& flight : flights){ adj[flight[0]].push_back({flight[1], flight[2]}); } priority_queue<pair<int,pair<int,int>>, vector<pair<int,pair<int,int>>>, cmp> pq; pq.push({src, {0, 0}}); vector<vector<int>> dist(n, vector<int>(K+2, INT_MAX)); dist[src][0] = 0; while(!pq.empty()){ auto top = pq.top(); pq.pop(); int node = top.first; int edge = top.second.first; int stops = top.second.second; if(node == dst) return edge; if(stops > K) continue; for(auto& [nbrnode, nbrdist] : adj[node]){ if(edge + nbrdist < dist[nbrnode][stops+1]){ dist[nbrnode][stops+1] = edge + nbrdist; pq.push({nbrnode, {dist[nbrnode][stops+1], stops+1}}); } } } return -1; } };
Leave a Comment