मान लीजिए कि हमारे पास m उड़ानों से जुड़े n शहर हैं। प्रत्येक उड़ान यू से शुरू होती है और मूल्य डब्ल्यू के साथ वी पर पहुंचती है। यदि हमारे पास सभी शहर और उड़ानें हैं, साथ में शहर का स्रोत और गंतव्य dst, तो यहां हमारा कार्य src से dst तक k स्टॉप तक की सबसे सस्ती कीमत खोजना है। अगर ऐसा कोई रास्ता नहीं है, तो वापसी -1.
इसलिए, यदि इनपुट n =3, किनारों =[[0,1,100], [1,2,100], [0,2,500]], src =0, dst =2, k =1 जैसा है, तो आउटपुट होगा 200
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
-
डेटा नामक एक डेटा संरचना बनाएं, इसमें नोड, जिला और वैल हो सकता है
-
एक 2डी सरणी लागत परिभाषित करें
-
लागत:=ऑर्डर की एक 2D सरणी (n + 1) x (K + 10) इसे अनंत से भरें
-
एक 3D सरणी ग्राफ़ परिभाषित करें
-
इनिशियलाइज़ i :=0 के लिए, जब i <फ्लाइट्स का आकार, अपडेट (i 1 से बढ़ाएँ), करें -
-
आप :=उड़ानें[i, 0]
-
v:=उड़ानें[i, 1]
-
ग्राफ़ के अंत में {v, उड़ानें[i, 2] } डालें[u]
-
-
एक प्राथमिकता कतार को परिभाषित करें q
-
डेटा (src, 0, 0) को q में डालें
-
लागत [src, 0] :=0
-
उत्तर :=-1
-
जबकि (नहीं q खाली है), करें -
-
अस्थायी:=q का शीर्ष तत्व
-
वक्र:=अस्थायी.नोड
-
q से तत्व हटाएं
-
जिला :=temp.dist
-
यदि curr dst के समान है, तो -
-
वापसी अस्थायी लागत
-
-
(दूरी में 1 से वृद्धि करें)
-
यदि जिला> K + 1, तो -
-
निम्नलिखित भाग पर ध्यान न दें, अगले पुनरावृत्ति पर जाएं
-
-
इनिशियलाइज़ करने के लिए मैं:=0, जब मैं <ग्राफ का आकार [कर्र], अपडेट (i 1 से बढ़ाएँ), करें -
-
पड़ोसी:=ग्राफ [कर्र, आई, 0]
-
अगर लागत [पड़ोसी, जिला]> लागत [कर, जिला - 1] + ग्राफ [कर, आई, 1], तो -
-
लागत [पड़ोसी, जिला]:=लागत [कर, जिला - 1] + ग्राफ [कर, आई, 1]
-
डेटा (पड़ोसी, जिला, लागत [पड़ोसी, जिला]) को क्यू में डालें
-
-
-
-
वापसी -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