Find the City With the Smallest Number of Neighbors at a Threshold Distance ใน C++

ให้ n เมือง (0..n-1) และ edges = [from, to, weight] (Bidirectional Weighted Graph) และ distanceThreshold

หา **City ที่มีจำนวนเพื่อนบ้าน (Reachable Cities) น้อยที่สุด** ภายในระยะทาง ≤ Threshold ถ้ามีหลายเมือง -> คืน **Index สูงสุด**

ตัวอย่าง

n=4, edges=[[0,1,3],[1,2,1],[1,3,4],[2,3,1]], threshold=4

Shortest Paths:
0: to 1(3), 2(4), 3(5) -> Neighbors ≤4: {1,2} Count=2
1: to 0(3), 2(1), 3(2) -> Neighbors ≤4: {0,2,3} Count=3
2: to 0(4), 1(1), 3(1) -> Neighbors ≤4: {0,1,3} Count=3
3: to 1(2), 2(1), 0(5) -> Neighbors ≤4: {1,2} Count=2

City 0 and 3 have Count=2 (Min). Return Max Index = 3.
Output: 3

แนวทาง: Floyd-Warshall Algorithm (All-Pairs Shortest Path)

n ≤ 100 -> Floyd-Warshall O(N³) = 1e6 Operations พอดี

1. Init dist[n][n] = INF, dist[i][i]=0, dist[u][v]=dist[v][u]=w
2. Triple Loop k, i, j: dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
3. Count Neighbors: สำหรับแต่ละ i นับ j != i ที่ dist[i][j] <= threshold
4. Track Min Count, Tie-break: Max Index

ตัวอย่างโค้ด C++

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    int findTheCity(int n, vector<vector<int>>& edges, int threshold) {
        const int INF = 1e7;
        vector<vector<int>> dist(n, vector<int>(n, INF));

        for (int i = 0; i < n; i++) dist[i][i] = 0;
        for (auto& e : edges) {
            dist[e[0]][e[1]] = e[2];
            dist[e[1]][e[0]] = e[2];
        }

        // Floyd-Warshall
        for (int k = 0; k < n; k++)
            for (int i = 0; i < n; i++)
                for (int j = 0; j < n; j++)
                    if (dist[i][k] + dist[k][j] < dist[i][j])
                        dist[i][j] = dist[i][k] + dist[k][j];

        int ans = -1, minCount = INT_MAX;
        for (int i = 0; i < n; i++) {
            int count = 0;
            for (int j = 0; j < n; j++)
                if (i != j && dist[i][j] <= threshold) count++;

            if (count <= minCount) { // <= for tie-breaking: larger index wins
                minCount = count;
                ans = i;
            }
        }
        return ans;
    }
};

Input / Output

Input:  4 [[0,1,3],[1,2,1],[1,3,4],[2,3,1]] 4
Output: 3

ความซับซ้อน (Complexity)

• Time: O(N³) — Floyd-Warshall (N ≤ 100)
• Space: O(N²) — Distance Matrix

Alternative: Dijkstra from Each Node

O(N * (E log V)) สำหรับ Sparse Graph เร็วกว่า แต่ N=100 Floyd-Warshall เขียนง่ายและพอครับ