मान लीजिए, n शहर हैं और शहरों के बीच m सड़कें हैं। m सड़कें हमें सड़कों के एक ऐरे में दी गई हैं जहां सड़कें {स्रोत, गंतव्य, वजन} प्रारूप में हैं। अब, हम एक ट्रिपलेट (s, t, k) को परिभाषित करते हैं जहां s, t, और k शहर हैं। अब हमें शहर s से शहर t तक पहुंचने के लिए आवश्यक न्यूनतम समय की गणना करनी है। s से t पर जाने के लिए, केवल 1 से k तक के शहरों का दौरा किया जा सकता है। यदि शहर t, s से पहुंच योग्य नहीं है, तो हम 0 वापस करते हैं। हमें सभी ट्रिपलेट (s, t, k) के लिए न्यूनतम समय की गणना करनी है, और उनका योग प्रिंट करना है।
उदाहरण के लिए, यदि इनपुट n = 4, m = 2, edges = {{1, 2, 5}, {2, 3, 4}, {3, 4, 3}} है, तो आउटपुट 63 होगा।
चरण
इसे हल करने के लिए, हम निम्नलिखित चरणों का पालन करेंगे:
मान अनंत से प्रारंभ एक 2D ऐरे dvec परिभाषित करें i := 0 से n-1 तक, करें: dvec[i, i] := 0 i := 0 से m-1 तक, करें: a := edges[i] का पहला मान b := edges[i] का दूसरा मान c := edges[i] का तीसरा मान a और b को 1 से घटाएं dvec[a, b] := c res := 0 k := 0 से n-1 तक, करें: i := 0 से n-1 तक, करें: j := 0 से n-1 तक, करें: dvec[i, j] := dvec[i, j] और dvec[i, k] + dvec[k, j] का न्यूनतम यदि dvec[i, j], अनंत के बराबर नहीं है, तो: res := res + dvec[i, j] print(res)
उदाहरण
बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें:
#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