ধরুন আমাদের কাছে একই আকারের খরচ_থেকে এবং খরচ_থেকে দুটি তালিকা রয়েছে যেখানে প্রতিটি সূচক i একটি শহরকে প্রতিনিধিত্ব করে। এটি শহর i থেকে j পর্যন্ত একটি একমুখী রাস্তা তৈরি করছে এবং তাদের খরচ হচ্ছে costs_from[i] + costs_to[j]। আমাদের কাছে প্রান্তগুলির একটি তালিকাও রয়েছে যেখানে প্রতিটি প্রান্তে [x, y] রয়েছে যা নির্দেশ করে যে ইতিমধ্যেই শহর x থেকে y পর্যন্ত একটি একমুখী রাস্তা রয়েছে। আমরা যদি শহর 0 থেকে যেকোনো শহরে যেতে চাই, তাহলে আমাদের প্রয়োজনীয় রাস্তা তৈরি করতে ন্যূনতম খরচ খুঁজে বের করতে হবে।
সুতরাং, ইনপুট যদি হয় costs_from =[6, 2, 2, 12] costs_to =[2, 2, 3, 2] edges =[[0, 3]], তাহলে আউটপুট হবে 13, যেমন আমরা যেতে পারি। 9 এর খরচের জন্য 0 থেকে 2 পর্যন্ত। এর পরে, আমরা 4 খরচের জন্য 2 থেকে 1 পর্যন্ত যেতে পারি। এবং আমাদের ইতিমধ্যে 0 থেকে 3-এ যাওয়ার রাস্তা রয়েছে। সুতরাং মোট হল 9 + 4 =13।
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
- n :=costs_from এর আকার
- ret :=0
- দুটি মানচিত্রের প্রান্ত এবং রেজগুলি সংজ্ঞায়িত করুন
- সমস্ত আইটেমের জন্য এটি g:
- প্রান্তের শেষে এটি[1] প্রবেশ করান[এটি[0]]
- এটি ঢোকান[0] রেডজের শেষে[এটি[1]]
- from_cost :=inf
- একটি পরিদর্শন করা সেট সংজ্ঞায়িত করুন এবং আরেকটি সেট পৌঁছানো যায়
- একটি ফাংশন dfs সংজ্ঞায়িত করুন, এটি একটি সংখ্যা নেবে i
- যদি আমাকে পরিদর্শন করা না হয় এবং আমি পৌঁছাতে না পারি, তাহলে:
- আমি ভিজিটেড ইনসার্ট করুন
- প্রান্তের সমস্ত j-এর জন্য[i], করুন
- dfs(j)
- po-এর শেষে i ঢোকান
- যদি আমাকে পরিদর্শন করা না হয় এবং আমি পৌঁছাতে না পারি, তাহলে:
- একটি ফাংশন dfs2 সংজ্ঞায়িত করুন, এটি একটি সংখ্যা নেবে i
- যদি আমাকে পরিদর্শন করা হয়, তাহলে
- সত্য ফেরত দিন
- যদি আমি পৌঁছাতে পারি
- মিথ্যে ফেরত দিন
- আমাকে পরিদর্শন করা হয়েছে বলে চিহ্নিত করুন এবং আমি পৌঁছানোর যোগ্য হিসেবে চিহ্নিত করুন
- ret :=সত্য
- সকল j এর জন্য রেডজেস[i], করুন
- ret :+ ret AND dfs2(j)
- রিটার্ন রিটার্ন
- একটি সারি q সংজ্ঞায়িত করুন
- পৌছাতে 0 ঢোকান এবং q তে 0 ঢোকান
- যখন (q খালি নয়), করবেন:
- নোড :=q এর প্রথম উপাদান
- q থেকে উপাদান মুছুন
- প্রত্যেক i-এর জন্য প্রান্ত [নোড]
- যদি আমি পৌঁছানো সম্ভব না হয়, তাহলে:
- আমি পৌঁছানোর মধ্যে ঢোকান, q-তে i ঢোকান
- from_cost :=সর্বনিম্ন from_cost এবং costs_from[node]
- যদি আমি পৌঁছানো সম্ভব না হয়, তাহলে:
- গ্লোবাল_মিন :=খরচ_থেকে ন্যূনতম উপাদান
- ret :=ret + from_cost - global_min
- একটি অ্যারে po সংজ্ঞায়িত করুন
- আমি 0 থেকে n রেঞ্জের জন্য, কর
- dfs(i)
- অ্যারে po বিপরীত করুন
- po তে প্রতিটি i এর জন্য, করুন
- যদি আমি পৌঁছাতে পারি, তাহলে:
- পরবর্তী পুনরাবৃত্তির জন্য যান
- পরিদর্শন করা অ্যারে সাফ করুন
- প্রাথমিক :=dfs2(i)
- প্রাথমিক সত্য হলে, তারপর:
- সর্বোত্তম :=inf
- পরিদর্শন করা প্রতিটি j-এর জন্য:
- সর্বোত্তম :=সর্বনিম্ন সেরা এবং খরচ_থেকে[j]
- ret :=ret + global_min + সেরা
- যদি আমি পৌঁছাতে পারি, তাহলে:
- রিটার্ন রিটার্ন
আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -
উদাহরণ
#include
using namespace std;
class Solution {
public:
int solve(vector& costs_from, vector& costs_to, vector>& g) {
int n = costs_from.size();
int ret = 0;
map> edges;
map> redges;
for (auto& it : g) {
edges[it[0]].push_back(it[1]);
redges[it[1]].push_back(it[0]);
}
int from_cost = INT_MAX;
set visited;
set reachable;
queue q;
reachable.insert(0);
q.push(0);
while (!q.empty()) {
int node = q.front();
q.pop();
for (int i : edges[node]) {
if (!reachable.count(i)) {
reachable.insert(i);
q.push(i);
}
}
from_cost = min(from_cost, costs_from[node]);
}
int global_min = *min_element(costs_from.begin(), costs_from.end());
ret += from_cost - global_min;
vector po;
function dfs;
dfs = [&](int i) {
if (!visited.count(i) && !reachable.count(i)) {
visited.insert(i);
for (int j : edges[i]) {
dfs(j);
}
po.push_back(i);
}
};
for (int i = 0; i < n; i++) dfs(i);
reverse(po.begin(), po.end());
function dfs2;
dfs2 = [&](int i) {
if (visited.count(i)) return true;
if (reachable.count(i)) return false;
visited.insert(i);
reachable.insert(i);
bool ret = true;
for (int j : redges[i]) {
ret &= dfs2(j);
}
return ret;
};
for (int i : po) {
if (reachable.count(i)) continue;
visited.clear();
bool initial = dfs2(i);
if (initial) {
int best = INT_MAX;
for (int j : visited) {
best = min(best, costs_to[j]);
}
ret += global_min + best;
}
}
return ret;
}
};
int solve(vector& costs_from, vector& costs_to, vector>& edges) {
return (new Solution())->solve(costs_from, costs_to, edges);
}
int main(){
vector costs_from = {6, 2, 2, 12};
vector costs_to = {2, 2, 3, 2};
vector> edges = {{0, 3}};
cout << solve(costs_from, costs_to, edges);
} ইনপুট
{6, 2, 2, 12}, {2, 2, 3, 2}, {{0, 3}} আউটপুট
13
