_1334. Find the City With the Smallest Number of Neighbors at a Threshold Distance.md

1334. Find the City With the Smallest Number of Neighbors at a Threshold Distance

All prompts are owned by LeetCode. To view the prompt, click the title link above.

Back to top

---

First completed : July 26, 2024

Last updated : July 26, 2024

---

Related Topics : Dynamic Programming, Graph, Shortest Path

Acceptance Rate : 68.65 %

---

Essentially did an all points shortest paths up until the total path length exceeds the distance threshold provided.

---

Solutions

• m1334 Daily.py

Python

m1334 Daily.py

class Solution:
    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
        routes = [[] for _ in range(n)]

        for a, b, w in edges :
            routes[a].append((b, w))
            routes[b].append((a, w))

        cityWithFewest = inf
        cityNo = -1

        # i = source city
        for i in range(n) :
            visited = set()
            toVisit = [(0, i)]       # heap

            while toVisit :
                dist, currCity = heapq.heappop(toVisit)

                if currCity in visited :
                    continue

                visited.add(currCity)

                for nextCity, w in routes[currCity] :
                    if nextCity not in visited and w + dist <= distanceThreshold :
                        heapq.heappush(toVisit, (w + dist, nextCity))

            if len(visited) - 1 <= cityWithFewest :
                cityWithFewest = len(visited) - 1
                cityNo = i

        return city