ค้นหาเมืองที่มีเพื่อนบ้านน้อยที่สุดในระยะทางที่กำหนดใน C++

สมมติว่ามี n เมืองที่มีตัวเลขตั้งแต่ 0 ถึง n-1 หากเรามีขอบอาร์เรย์โดยที่ 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 มีเมืองใกล้เคียง 2 เมืองที่ระยะทาง =4 แต่เราต้องกลับเมือง 3 เนื่องจากมีตัวเลขมากที่สุด

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• กำหนดเมทริกซ์กำลังสองของคำสั่ง n x n ที่เรียกว่า dp แล้วเติมด้วยอนันต์

• สร้างเมทริกซ์ที่อยู่ติดกัน (เมทริกซ์ต้นทุน) ของกราฟและจัดเก็บไว้ใน dp

• ret :=0 และ cnt :=อินฟินิตี้

• สำหรับ k ในช่วง 0 ถึง n – 1

  • สำหรับฉันอยู่ในช่วง 0 ถึง n – 1

    • สำหรับ j ในช่วง 0 ถึง n – 1

      • ถ้า 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

  • อุณหภูมิ :=0

  • สำหรับ j ในช่วง 0 ถึง n – 1

    • 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

ผลลัพธ์

3