मान लीजिए हमारे पास n शहर हैं जो m उड़ानों से जुड़े हैं। प्रत्येक उड़ान u से शुरू होकर v पर पहुंचती है जिसकी कीमत w है। यदि हमारे पास सभी शहर और उड़ानें हैं, साथ में प्रारंभिक शहर src और गंतव्य dst, तो हमारा काम src से dst तक अधिकतम k स्टॉप के साथ सबसे सस्ती कीमत ढूंढना है। यदि ऐसा कोई मार्ग नहीं है, तो -1 लौटाएं।
उदाहरण के लिए, यदि इनपुट n = 3, edges = [[0,1,100],[1,2,100],[0,2,500]], src = 0, dst = 2, k = 1 है, तो आउटपुट 200 होगा।
हल करने की विधि
हम डिज्क्स्ट्रा एल्गोरिदम का संशोधित संस्करण उपयोग करेंगे:
- नोड, दूरी, और लागत रखने के लिए एक डेटा संरचना Data परिभाषित करें।
- लागत मैट्रिक्स cost परिभाषित करें, आकार (n+1) x (K+10), अनंत से भरा।
- ग्राफ को आसन्न सूची के रूप में बनाएं।
- न्यूनतम-हीप प्राथमिकता कतार q का उपयोग करें।
- Data(src, 0, 0) को q में डालें, cost[src][0] = 0 सेट करें।
- जब तक q खाली न हो:
- शीर्ष तत्व निकालें।
- यदि वर्तमान नोड dst है, तो लागत लौटाएं।
- दूरी बढ़ाएं, यदि दूरी > K+1 तो जारी रखें।
- पड़ोसियों के लिए, यदि नई लागत कम है, तो अपडेट करें और q में डालें।
- -1 लौटाएं।
उदाहरण
बेहतर समझ के लिए निम्न कार्यान्वयन देखें:
#include <bits/stdc++.h> using namespace std; struct Data{ int node, dist, cost; Data(int a, int b, int c){ node = a; dist = b; cost = c; } }; struct Comparator{ bool operator() (Data a, Data b) { return !(a.cost < b.cost); } }; class Solution { public: vector<vector<int>> cost; int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int K) { cost = vector<vector<int> >(n + 1, vector<int>(K + 10, INT_MAX)); vector<vector<int> > graph[n]; for (int i = 0; i < flights.size(); i++) { int u = flights[i][0]; int v = flights[i][1]; graph[u].push_back({ v, flights[i][2] }); } priority_queue<Data, vector<Data>, Comparator> q; q.push(Data(src, 0, 0)); cost[src][0] = 0; int ans = -1; while (!q.empty()) { Data temp = q.top(); int curr = temp.node; q.pop(); int dist = temp.dist; if (curr == dst) return temp.cost; dist++; if (dist > K + 1) continue; for (int i = 0; i < graph[curr].size(); i++) { int neighbour = graph[curr][i][0]; if (cost[neighbour][dist] > cost[curr][dist - 1] + graph[curr][i][1]) { cost[neighbour][dist] = cost[curr][dist - 1] + graph[curr][i][1]; q.push(Data(neighbour, dist, cost[neighbour][dist])); } } } return -1; } }; main(){ Solution ob; vector<vector<int>> v = {{0,1,100},{1,2,100},{0,2,500}}; cout << (ob.findCheapestPrice(3, v, 0, 2, 1)); }
इनपुट
3, {{0,1,100},{1,2,100},{0,2,500}}, 0, 2, 1
आउटपुट
200
