ধরুন, m রাস্তার সাথে যুক্ত শহরগুলির সংখ্যা n আছে। রাস্তাগুলি একমুখী, রাস্তাগুলি কেবল উৎস থেকে গন্তব্যে যেতে পারে, বিপরীত দিকে নয়। রাস্তাগুলি অ্যারে 'রাস্তা' ফরম্যাটে {উৎস, গন্তব্য} দেওয়া হয়েছে৷ এখন শহরগুলোতে বিভিন্ন দামে গম বিক্রি হয়। শহর জুড়ে গমের দাম একটি অ্যারে 'দাম'-এ দেওয়া আছে, যেখানে i-th মান হল i-th শহরে গমের দাম। এখন, একজন মুসাফির যেকোন শহর থেকে গম ক্রয় করতে পারে এবং যে কোন শহরে (যদি জায়েয হয়) পৌঁছে বিক্রি করতে পারে। আমাদের খুঁজে বের করতে হবে গম ব্যবসা করে ভ্রমণকারীর দ্বারা লাভের সর্বাধিক পরিমাণ।
সুতরাং, যদি ইনপুটটি হয় n =5, m =3, মূল্য ={4, 6, 7, 8, 5}, রাস্তা ={{1, 2}, {2, 3}, {2, 4}, {4, 5}}, তাহলে আউটপুট হবে 4।
যদি ভ্রমণকারী প্রথম শহরে গম কিনে চতুর্থ শহরে বিক্রি করে, তাহলে মোট লাভের পরিমাণ হবে 4।
পদক্ষেপ
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
Define one 2D array graph of size nxn.
for initialize i := 0, when i < m, update (increase i by 1), do:
x := first value of roads[i]
y := second value of roads[i]
decrease x, y by 1
insert y at the end of graph[x]
Define an array tp of size n initialized with value negative infinity.
for initialize i := 0, when i < n, update (increase i by 1), do:
for each value u in graph[i], do:
tp[u] := minimum of ({tp[u], tp[i], price[i]})
res := negative infinity
for initialize i := 0, when i < n, update (increase i by 1), do:
res := maximum of (res and price[i] - tp[i])
return res উদাহরণ
আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -
#include <bits/stdc++.h>
using namespace std;
int solve(int n, int m, vector<int> price, vector<pair<int, int>>
roads){
vector<vector<int>> graph(n);
for(int i = 0; i < m; i++){
int x, y;
x = roads[i].first;
y = roads[i].second;
x--, y--;
graph[x].push_back(y);
}
vector<int> tp(n, int(INFINITY));
for(int i = 0; i < n; i++){
for(int u : graph[i]){
tp[u] = min({tp[u], tp[i], price[i]});
}
}
int res = -int(INFINITY);
for(int i = 0; i < n; i++){
res = max(res, price[i] - tp[i]);
}
return res;
}
int main() {
int n = 5, m = 3;
vector <int> price = {4, 6, 7, 8, 5};
vector<pair<int, int>> roads = {{1, 2}, {2, 3}, {2, 4}, {4, 5}};
cout<< solve(n, m, price, roads);
return 0;
} ইনপুট
5, 3, {4, 6, 7, 8, 5}, {{1, 2}, {2, 3}, {2, 4}, {4, 5}}
আউটপুট
4
