Flipkart | Find the City With the Smallest Number of Neighbors at a Threshold Distance

link:-  https://leetcode.com/problems/find-the-city-with-the-smallest-number-of-neighbors-at-a-threshold-distance/

class Solution:
    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
        mat=[[1e12]*n for i in range(n)]
        for u,v,w in edges:
            mat[u][v]=mat[v][u]=w
        for k in range(n):
            for i in range(n):
                for j in range(n):
                    if i==j:
                        continue
                    mat[i][j]=min(mat[i][j],mat[i][k]+mat[k][j])
        
        maxi=1e12
        ans=n+1 
        for i in range(n):               
            ct=0
            for j in range(n):
                if mat[i][j]<=distanceThreshold:
                    ct+=1
            if ct<=maxi:
                ans=i
                maxi=ct
        # print(mat)    
        return ans