C++で2つの異なる良好なノードの任意のペア間の最短距離を見つけます

N個の異なるノードとM個のエッジを持つ特定の重み付き無向グラフがあるとすると、一部のノードは適切なノードです。 2つの異なる良好なノードの任意のペア間の最短距離を見つける必要があります。与えられた図では、次のグラフの黄色は適切なノードと見なされます。

したがって、入力が次のような場合

その場合、出力は11になります。これは、適切なノードのペアとそれらの間の距離が次のとおりであるためです。（1から3）距離は11、（3から5）距離は13、（1から5）距離は24、そのうち11が最小です。

これを解決するには、次の手順に従います-

• N：=100005

• MAX_VAL：=99999999

• 1つの優先キューを作成するq

• 結果：=MAX_VAL

• 初期化i：=1の場合、i <=nの場合、更新（iを1増やします）、実行-

  • good_verts [i]がfalseの場合、-

    • 次の部分を無視し、次の反復にスキップします

  • 初期化j：=1の場合、j <=nの場合、更新（jを1増やします）、実行-

    • dist [j]：=MAX_VAL

    • vis [j]：=0

  • dist [i]：=0

  • （qが空ではない）間、-

    • qから要素を削除

  • {0、i}をq

    に挿入します

  • 良い：=0

  • （qが空ではない）間、-

    • v：=qの最上位要素

    • qから要素を削除

    • vis [v]が真の場合、-

      • 次の部分を無視し、次の反復にスキップします

    • vis [v]：=1

    • good：=good +（good_verts [v]がtrueの場合は1、それ以外の場合は0）

    • dist [v]>の結果の場合、-

      • ループから出てきます

    • goodが2およびgood_verts[v]と同じである場合、-

      • 結果：=結果とdist [v]

        の最小値

      • ループから出てきます

    • 初期化j：=0の場合、j <グラフのサイズ[v]の場合、更新（jを1増やします）、実行-

      • to：=graph [v、j] .first

      • 重み：=グラフ[v、j] .second

      • dist [v] + weight

        • 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;

出力

7