Tìm Thành Phố Có Số Lượng Hàng Xóm Nhỏ Nhất Tại Khoảng Cách Ngưỡng Trong C++

Giả sử có n thành phố đánh số 0 đến n-1. Mảng edges với edges[i] = [fromi, toi, weighti] biểu diễn cạnh hai chiều có trọng số giữa fromi và toi. Cho ngưỡng khoảng cách distanceThreshold. Tìm thành phố có số lượng thành phố khác có thể đến được qua đường đi với khoảng cách ≤ distanceThreshold nhỏ nhất. Nếu nhiều thành phố như vậy, trả về thành phố có số thứ tự lớn nhất.

Ví dụ như hình, n=4, distanceThreshold=4 → 3.

Các thành phố lân cận trong ngưỡng 4:

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

Thành phố 0 và 3 đều có 2 láng giềng, chọn 3 vì số lớn hơn.

Để giải quyết, chúng ta làm theo các bước:

• Tạo ma trận dp n x n điền vô cực.

• Xây dựng ma trận kề (ma trận chi phí) từ edges lưu vào dp.

• ret = 0, cnt = vô cực.

• Floyd-Warshall: với k,i,j từ 0 đến n-1: nếu i==j continue; nếu dp[i][j] > dp[i][k] + dp[k][j] thì cập nhật dp[i][j] và dp[j][i].

• Với i từ 0 đến n-1: temp = 0; với j từ 0 đến n-1: nếu dp[i][j] <= t thì temp++; nếu temp <= cnt thì cnt = temp, ret = i.

• Trả về ret.

Ví dụ (C++)

Hãy xem triển khai sau để hiểu rõ hơn:

#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;
    }
};

int 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));
}

Đầu vào

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

Đầu ra

3