Computer >> 컴퓨터 >  >> 프로그램 작성 >> C++

C++에서 두 개의 서로 다른 좋은 노드 쌍 사이의 최단 거리 찾기

<시간/>

N개의 서로 다른 노드와 M개의 간선이 있는 가중치가 부여된 무방향 그래프가 있다고 가정하고 일부 노드는 좋은 노드입니다. 우리는 두 개의 서로 다른 좋은 노드 쌍 사이의 최단 거리를 찾아야 합니다. 주어진 다이어그램에서 다음 그래프의 노란색은 좋은 노드로 간주됩니다.

따라서 입력이 다음과 같으면

C++에서 두 개의 서로 다른 좋은 노드 쌍 사이의 최단 거리 찾기

좋은 노드의 쌍과 그들 사이의 거리가 다음과 같기 때문에 출력은 11이 됩니다. (1에서 3) 거리가 11, (3에서 5) 거리가 13, (1에서 5) 거리가 24이고, 그 중 11개가 최소값입니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

  • N :=100005

  • MAX_VAL :=99999999

  • 하나의 우선 순위 대기열 생성 q

  • 결과 :=MAX_VAL

  • initialize i :=1의 경우, i <=n일 때 업데이트(i를 1만큼 증가), −

    • good_verts[i]가 거짓이면 -

      • 다음 부분은 무시하고 다음 반복으로 건너뜁니다.

    • j 초기화:=1의 경우 j <=n일 때 업데이트(j를 1만큼 증가), −

      • dist[j] :=MAX_VAL

      • vis[j] :=0

    • dist[i] :=0

    • 동안(q가 비어 있지 않음) -

      를 수행합니다.
      • q에서 요소 삭제

    • q에 { 0, i } 삽입

    • 좋은 :=0

    • 동안(q가 비어 있지 않음) -

      를 수행합니다.
      • v :=q의 최상위 요소

      • q에서 요소 삭제

      • vis[v]가 참이면 -

        • 다음 부분은 무시하고 다음 반복으로 건너뜁니다.

      • vis[v] :=1

      • good :=good + (good_verts[v]가 참이면 1, 그렇지 않으면 0)

      • dist[v]> 결과이면 -

        • 루프에서 나오세요

      • good이 2 및 good_verts[v]와 같으면 -

        • result :=결과의 최소값과 dist[v]

        • 루프에서 나오세요

      • j 초기화의 경우:=0, j <그래프[v]의 크기일 때 업데이트(j를 1만큼 증가), 수행 -

        • to :=그래프[v, j].첫 번째

        • 가중치 :=그래프[v, j].초

        • dist[v] + weight

          • dist[to] :=dist[v] + 가중치

          • q에 { dist[to], to } 삽입

  • 반환 결과

예시

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

#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