মান লিখুন: nটি সিটি এবং mটি রোড আছে। রোডগুলো {source, destination, weight} ফরম্যাটে দেওয়া আছে। এখন একটি ট্রিপলেট (s, t, k) সংজ্ঞায়িত করা হয়েছে যেখানে s, t, k সিটি। এখন s থেকে t-এ যেতে ন্যূনতম সময় বের করতে হবে। s থেকে t-এ যেতে শুধু ১ থেকে k নম্বর সিটিগুলোই ভিজিট করা যাবে। যদি t s-থেকে পৌঁছানো না যায়, তবে ০ রিটার্ন করুন। সব ট্রিপলেট (s, t, k)-এর জন্য ন্যূনতম সময় বের করে তাদের যোগফল প্রিন্ট করতে হবে।
উদাহরণ
যদি ইনপুট হয় n = 4, m = 2, edges = {{1, 2, 5}, {2, 3, 4}, {3, 4, 3}}, তবে আউটপুট হবে 63।
সমাধানের ধাপসমূহ
dvec ২ডি অ্যারে ইনফিনিট দিয়ে ইনিশিয়ালাইজ
for i := 0 থেকে n-1: dvec[i][i] := 0
for i := 0 থেকে m-1:
a := edges[i].first, b := edges[i].second, c := edges[i].third
a--, b--
dvec[a][b] := c
res := 0
for k := 0 থেকে n-1:
for i := 0 থেকে n-1:
for j := 0 থেকে n-1:
dvec[i][j] := min(dvec[i][j], dvec[i][k] + dvec[k][j])
যদি dvec[i][j] != infinity:
res += dvec[i][j]
res প্রিন্ট করুন
C++ বাস্তবায়ন
#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9;
void solve(int n, int m, vector<tuple<int, int, int>> edges) {
vector<vector<int>> dvec(n, vector<int>(n, INF));
for (int i = 0; i < n; i++) dvec[i][i] = 0;
for (int i = 0; i < m; i++) {
int a = get<0>(edges[i]);
int b = get<1>(edges[i]);
int c = get<2>(edges[i]);
a--; b--;
dvec[a][b] = c;
}
int res = 0;
for (int k = 0; k < n; k++) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
dvec[i][j] = min(dvec[i][j], dvec[i][k] + dvec[k][j]);
if (dvec[i][j] != INF) res += dvec[i][j];
}
}
}
cout << res << endl;
}
int main() {
int n = 4, m = 2;
vector<tuple<int, int, int>> edges = {{1, 2, 5}, {2, 3, 4}, {3, 4, 3}};
solve(n, m, edges);
return 0;
}
ইনপুট
4, 2, {{1, 2, 5}, {2, 3, 4}, {3, 4, 3}}
আউটপুট
63
