Formatted question description: https://leetcode.ca/all/1334.html
1334. Find the City With the Smallest Number of Neighbors at a Threshold Distance (Medium)
There are n
cities numbered from 0
to n-1
. Given the array edges
where edges[i] = [fromi, toi, weighti]
represents a bidirectional and weighted edge between cities fromi
and toi
, and given the integer distanceThreshold
.
Return the city with the smallest number of cities that are reachable through some path and whose distance is at most distanceThreshold
, If there are multiple such cities, return the city with the greatest number.
Notice that the distance of a path connecting cities i and j is equal to the sum of the edges' weights along that path.
Example 1:
Input: n = 4, edges = [[0,1,3],[1,2,1],[1,3,4],[2,3,1]], distanceThreshold = 4 Output: 3 Explanation: The figure above describes the graph. The neighboring cities at a distanceThreshold = 4 for each city are: City 0 -> [City 1, City 2] City 1 -> [City 0, City 2, City 3] City 2 -> [City 0, City 1, City 3] City 3 -> [City 1, City 2] Cities 0 and 3 have 2 neighboring cities at a distanceThreshold = 4, but we have to return city 3 since it has the greatest number.
Example 2:
Input: n = 5, edges = [[0,1,2],[0,4,8],[1,2,3],[1,4,2],[2,3,1],[3,4,1]], distanceThreshold = 2 Output: 0 Explanation: The figure above describes the graph. The neighboring cities at a distanceThreshold = 2 for each city are: City 0 -> [City 1] City 1 -> [City 0, City 4] City 2 -> [City 3, City 4] City 3 -> [City 2, City 4] City 4 -> [City 1, City 2, City 3] The city 0 has 1 neighboring city at a distanceThreshold = 2.
Constraints:
2 <= n <= 100
1 <= edges.length <= n * (n - 1) / 2
edges[i].length == 3
0 <= fromi < toi < n
1 <= weighti, distanceThreshold <= 10^4
- All pairs
(fromi, toi)
are distinct.
Related Topics:
Graph
Solution 1.
// OJ: https://leetcode.com/problems/find-the-city-with-the-smallest-number-of-neighbors-at-a-threshold-distance/
// Time: O(V * (E + VlogV))
// Space: O(E)
class Solution {
typedef pair<int, int> iPair;
unordered_map<int, vector<iPair>> graph;
int th, N, minNum = INT_MAX;
int dijkstra(int i) {
priority_queue<iPair, vector<iPair>, greater<iPair>> q;
vector<int> dist(N, INT_MAX);
q.push(make_pair(0, i));
dist[i] = 0;
while (q.size()) {
int u = q.top().second;
q.pop();
for (auto ne : graph[u]) {
int v = ne.first;
int w = ne.second;
if (dist[v] > dist[u] + w) {
dist[v] = dist[u] + w;
q.push(make_pair(dist[v], v));
}
}
}
int cnt = 0;
for (int j = 0; j < N; ++j) {
if (j != i && dist[j] <= th) ++cnt;
}
return cnt;
}
public:
int findTheCity(int n, vector<vector<int>>& edges, int distanceThreshold) {
th = distanceThreshold;
N = n;
for (auto e : edges) {
m[e[0]].push_back(make_pair(e[1], e[2]));
m[e[1]].push_back(make_pair(e[0], e[2]));
}
int ans = 0;
for (int i = 0; i < n; ++i) {
int cnt = dijkstra(i);
if (cnt <= minNum) {
minNum = cnt;
ans = i;
}
}
return ans;
}
};
Solution 2. Floyd-Warshall
// OJ: https://leetcode.com/problems/find-the-city-with-the-smallest-number-of-neighbors-at-a-threshold-distance/
// Time: O(N^3)
// Space: O(N^2)
class Solution {
public:
int findTheCity(int n, vector<vector<int>>& E, int k) {
vector<vector<int>> d(n, vector<int>(n, (int) 1e6));
for (int i = 0; i < n; ++i) d[i][i] = 0;
for (auto &e : E) {
d[e[0]][e[1]] = d[e[1]][e[0]] = e[2];
}
for (int i = 0; i < n; ++i) {
for (int u = 0; u < n; ++u) {
for (int v = 0; v < n; ++v) {
d[u][v] = min(d[u][v], d[u][i] + d[i][v]);
}
}
}
int ans = 0, minCnt = n;
for (int i = 0; i < n; ++i) {
int cnt = 0;
for (int j = 0; j < n; ++j) {
if (d[i][j] <= k) ++cnt;
}
if (cnt <= minCnt) {
minCnt = cnt;
ans = i;
}
}
return ans;
}
};
Java
-
class Solution { public int findTheCity(int n, int[][] edges, int distanceThreshold) { Map<Integer, List<int[]>> distancesMap = new HashMap<Integer, List<int[]>>(); for (int[] edge : edges) { int city1 = edge[0], city2 = edge[1], distance = edge[2]; List<int[]> list1 = distancesMap.getOrDefault(city1, new ArrayList<int[]>()); List<int[]> list2 = distancesMap.getOrDefault(city2, new ArrayList<int[]>()); list1.add(new int[]{city2, distance}); list2.add(new int[]{city1, distance}); distancesMap.put(city1, list1); distancesMap.put(city2, list2); } int[] reachableCounts = new int[n]; for (int i = 0; i < n; i++) { int[] distances = getDistance(n, i, distancesMap); for (int distance : distances) { if (distance > 0 && distance <= distanceThreshold) reachableCounts[i]++; } } int minReachable = n - 1; for (int i = 0; i < n; i++) minReachable = Math.min(minReachable, reachableCounts[i]); int cityIndex = 0; for (int i = n - 1; i >= 0; i--) { if (reachableCounts[i] == minReachable) { cityIndex = i; break; } } return cityIndex; } public int[] getDistance(int n, int source, Map<Integer, List<int[]>> distancesMap) { int[] distances = new int[n]; for (int i = 0; i < n; i++) distances[i] = Integer.MAX_VALUE; distances[source] = 0; PriorityQueue<CityDistance> priorityQueue = new PriorityQueue<CityDistance>(); priorityQueue.offer(new CityDistance(source, 0)); while (!priorityQueue.isEmpty()) { CityDistance cityDistance = priorityQueue.poll(); int city = cityDistance.city, distance = cityDistance.distance; if (distance > distances[city]) continue; List<int[]> adjacentCities = distancesMap.getOrDefault(city, new ArrayList<int[]>()); for (int[] adjacentCity : adjacentCities) { int nextCity = adjacentCity[0], nextDistance = adjacentCity[1]; int newDistance = distance + nextDistance; if (newDistance < distances[nextCity]) { distances[nextCity] = newDistance; priorityQueue.offer(new CityDistance(nextCity, newDistance)); } } } return distances; } } class CityDistance implements Comparable<CityDistance> { public int city; public int distance; public CityDistance(int city, int distance) { this.city = city; this.distance = distance; } public int compareTo(CityDistance cityDistance2) { return this.distance - cityDistance2.distance; } }
-
// OJ: https://leetcode.com/problems/find-the-city-with-the-smallest-number-of-neighbors-at-a-threshold-distance/ // Time: O(V * (E + VlogV)) // Space: O(E) class Solution { typedef pair<int, int> iPair; unordered_map<int, vector<iPair>> graph; int th, N, minNum = INT_MAX; int dijkstra(int i) { priority_queue<iPair, vector<iPair>, greater<iPair>> q; vector<int> dist(N, INT_MAX); q.push(make_pair(0, i)); dist[i] = 0; while (q.size()) { int u = q.top().second; q.pop(); for (auto ne : graph[u]) { int v = ne.first; int w = ne.second; if (dist[v] > dist[u] + w) { dist[v] = dist[u] + w; q.push(make_pair(dist[v], v)); } } } int cnt = 0; for (int j = 0; j < N; ++j) { if (j != i && dist[j] <= th) ++cnt; } return cnt; } public: int findTheCity(int n, vector<vector<int>>& edges, int distanceThreshold) { th = distanceThreshold; N = n; for (auto e : edges) { m[e[0]].push_back(make_pair(e[1], e[2])); m[e[1]].push_back(make_pair(e[0], e[2])); } int ans = 0; for (int i = 0; i < n; ++i) { int cnt = dijkstra(i); if (cnt <= minNum) { minNum = cnt; ans = i; } } return ans; } };
-
print("Todo!")