C++에서 임계 거리에서 이웃 수가 가장 적은 도시 찾기

0에서 n-1까지 번호가 매겨진 n개의 도시가 있다고 가정합니다. edge[i] =[fromi, toi, weighti]인 배열 가장자리가 있는 경우 fromi와 toi 도시 사이의 양방향 가중 가장자리를 나타내고 정수 거리 임계값이 주어집니다. 우리는 어떤 경로를 통해 도달할 수 있는 가장 적은 수의 도시가 있고 그 거리가 최대 거리 임계값에 있는 도시를 찾아야 합니다. 그러한 도시가 둘 이상 있으면 가장 많은 도시를 반환합니다.

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

n이 4이고 거리 임계값도 4이면 출력은 3이 됩니다. 이는 -

각 도시에 대해 거리 임계값 =4에 있는 인접 도시는 -

C0 -> [C1, C2]
C1 -> [C0, C2, C3]
C2 -> [C0, C1, C3]
C3 -> [C1, C2]

도시 0과 3에는 거리 임계값 =4에 2개의 이웃 도시가 있지만 도시 3이 가장 많기 때문에 반환해야 합니다.

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

dp라고 하는 n x n 차수의 정사각 행렬을 정의하고 이것을 무한대로 채웁니다.
그래프의 인접 행렬(비용 행렬)을 생성하고 dp에 저장
ret :=0 및 cnt :=무한대
범위 0에서 n – 1까지의 k에 대해
- 0 ~ n – 1 범위의 i에 대해
  - 0 ~ n – 1 범위의 j에 대해
    - i =j이면 다음 반복으로 이동
    - dp[i, j]> dp[i, k] + dp[k, j]이면
      - dp[j, i] :=dp[i, k] + dp[k, j]
      - dp[i, j] :=dp[i, k] + dp[k, j]
0 ~ n - 1 범위의 i에 대해
- 온도 :=0
- 0 ~ n – 1 범위의 j에 대해
  - temp :=temp + 1 일 때 dp[i, j] <=t, 그렇지 않으면 temp가 동일하게 유지
- temp <=cnt이면 cnt :=temp 및 ret :=i
리턴 렛

예시(C++)

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

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   int findTheCity(int n, vector<vector<int>>& e, int t) {
      vector < vector <int> > dp(n, vector <int>(n, 1e7));
      for(int i = 0; i < e.size(); i++){
         int u = e[i][0];
         int v = e[i][1];
         int w = e[i][2];
         dp[u][v] = w;
         dp[v][u] = w;
      }
      int ret = 0;
      int cnt = INT_MAX;
      for(int k = 0; k < n; k++){
         for(int i = 0; i < n; i++){
            for(int j = 0; j < n; j++){
               if(i == j) continue;
               if(dp[i][j] > dp[i][k] + dp[k][j]){
                  dp[j][i] = dp[i][j] = (dp[i][k] + dp[k][j]);
               }
            }
         }
      }
      for(int i = 0; i < n; i++){
         int temp = 0;
         for(int j = 0; j < n; j++){
            temp += (dp[i][j] <= t);
         }
         if(temp <= cnt){
            cnt = temp;
            ret = i;
         }
      }
      return ret;
   }
};
main(){
   vector<vector<int>> v = {{0,1,3},{1,2,1},{1,3,4},{2,3,1}};
   Solution ob;
   cout << (ob.findTheCity(4, v, 4));
}

입력

4
[[0,1,3],[1,2,1],[1,3,4],[2,3,1]]
4