C++ में दो अलग-अलग गुड नोड्स की किसी भी जोड़ी के बीच सबसे छोटी दूरी खोजें

मान लीजिए हमारे पास N अलग-अलग नोड्स और M एजेज के साथ एक दिया गया वेटेड अनडायरेक्टेड ग्राफ है, कुछ नोड्स गुड नोड्स हैं। हमें किन्हीं दो अलग-अलग गुड नोड्स की जोड़ी के बीच सबसे छोटी दूरी खोजनी है। दिए गए आरेख में पीले नोड्स को गुड नोड्स माना जाता है।

उदाहरण के लिए, यदि इनपुट इस तरह का है:

तो आउटपुट 11 होगा, क्योंकि गुड नोड्स के जोड़े और उनके बीच की दूरी हैं: (1 से 3) दूरी 11, (3 से 5) दूरी 13, (1 से 5) दूरी 24, जिनमें से 11 न्यूनतम है।

इसे हल करने के लिए, हम निम्न चरणों का पालन करेंगे:

N := 100005
MAX_VAL := 99999999
एक प्रायोरिटी क्यू q बनाएं
रिजल्ट := MAX_VAL
i := 1 से n तक लूप करें:
- यदि good_verts[i] false है, तो अगली इटरेशन पर जाएं
- j := 1 से n तक लूप करें:
  - dist[j] := MAX_VAL
  - vis[j] := 0
- dist[i] := 0
- जब तक q खाली नहीं है, q से तत्व हटाएं
- { 0, i } को q में डालें
- good := 0
- जब तक q खाली नहीं है:
  - v := q का शीर्ष तत्व
  - q से तत्व हटाएं
  - यदि vis[v] true है, तो अगली इटरेशन पर जाएं
  - vis[v] := 1
  - good := good + (1 यदि good_verts[v] true है, अन्यथा 0)
  - यदि dist[v] > रिजल्ट, तो लूप से बाहर निकलें
  - यदि good 2 के बराबर है और good_verts[v] true है, तो:
    - रिजल्ट := रिजल्ट और dist[v] का न्यूनतम
    - लूप से बाहर निकलें
  - j := 0 से graph[v] के आकार - 1 तक लूप करें:
    - to := graph[v][j].first
    - वेट := graph[v][j].second
    - यदि dist[v] + वेट < dist[to], तो:
      - dist[to] := dist[v] + वेट
      - { dist[to], to } को q में डालें
रिजल्ट लौटाएं

उदाहरण

बेहतर समझ के लिए निम्न कार्यान्वयन देखें:

#include <bits/stdc++.h> using namespace std; #define N 100005 #define MAX_VAL 99999999 void insert_edge(vector<pair<int, int> > graph[], int x, int y, int weight) { graph[x].push_back({ y, weight }); graph[y].push_back({ x, weight }); } int get_min_dist(vector<pair<int, int> > graph[], int n, int dist[], int vis[], int good_verts[], int k) { priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int>>> q; int result = MAX_VAL; for (int i = 1; i <= n; i++) { if (!good_verts[i]) continue; for (int j = 1; j <= n; j++) { dist[j] = MAX_VAL; vis[j] = 0; } dist[i] = 0; while (!q.empty()) q.pop(); q.push({ 0, i }); int good = 0; while (!q.empty()) { int v = q.top().second; q.pop(); if (vis[v]) continue; vis[v] = 1; good += good_verts[v]; if (dist[v] > result) break; if (good == 2 and good_verts[v]) { result = min(result, dist[v]); break; } for (int j = 0; j < graph[v].size(); j++) { int to = graph[v][j].first; int weight = graph[v][j].second; if (dist[v] + weight < dist[to]) { dist[to] = dist[v] + weight; q.push({ dist[to], to }); } } } } return result; } int main() { int n = 5, m = 5; vector<pair<int, int> > graph[N]; insert_edge(graph, 1, 2, 3); insert_edge(graph, 1, 2, 3); insert_edge(graph, 2, 3, 4); insert_edge(graph, 3, 4, 1); insert_edge(graph, 4, 5, 8); int k = 3; int good_verts[N], vis[N], dist[N]; good_verts[1] = good_verts[3] = good_verts[5] = 1; cout << get_min_dist(graph, n, dist, vis, good_verts, k); }

इनपुट

n = 5, m = 5 insert_edge(graph, 1, 2, 3); insert_edge(graph, 1, 2, 3); insert_edge(graph, 2, 3, 4); insert_edge(graph, 3, 4, 1); insert_edge(graph, 4, 5, 8); k = 3 good_verts[1] = good_verts[3] = good_verts[5] = 1;