leetcode 周赛 173 5321. 阈值距离内邻居最少的城市 find the city with the smallest number of neighbors at a threshold distance

目录

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

Floyd（弗洛伊德）算法

class Solution:
    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
        to = {}
        for i in range(n): 
            to[i] = {}
        for e in edges:
            if e[2] <= distanceThreshold:
                if e[1] in to[e[0]]:
                    to[e[0]][e[1]] = min(to[e[0]][e[1]], e[2])
                else:
                    to[e[0]][e[1]] = e[2]
                if e[0] in to[e[1]]:
                    to[e[1]][e[0]] = min(to[e[1]][e[0]], e[2])
                else:
                    to[e[1]][e[0]] = e[2]
        flag = True
        while flag:
            flag = False
            for c in to:
                tl = list(to[c].items())
                for d1, v1 in tl:
                    for d2, v2 in to[d1].items():
                        if d2 == c: continue
                        if v1 + v2 <= distanceThreshold:
                            if d2 in to[c]:
                                if v2 + v1 < to[c][d2]:
                                    flag = True
                                    to[c][d2] = v1 + v2
                            else:
                                to[c][d2] = v1 + v2
                                flag = True
        mc = n + 1
        mid = -1
        for c in to:
            if len(to[c]) == mc and c > mid or len(to[c]) < mc:
                mc = len(to[c])
                mid = c
        return mid