{"id":6149,"date":"2020-01-26T22:58:54","date_gmt":"2020-01-27T06:58:54","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=6149"},"modified":"2020-01-28T23:50:22","modified_gmt":"2020-01-29T07:50:22","slug":"leetcode-1334-find-the-city-with-the-smallest-number-of-neighbors-at-a-threshold-distance","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/graph\/leetcode-1334-find-the-city-with-the-smallest-number-of-neighbors-at-a-threshold-distance\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 1334. Find the City With the Smallest Number of Neighbors at a Threshold Distance"},"content":{"rendered":"\n<figure class=\"wp-block-embed-youtube wp-block-embed is-type-video is-provider-youtube wp-embed-aspect-4-3 wp-has-aspect-ratio\"><div class=\"wp-block-embed__wrapper\">\n<iframe loading=\"lazy\" title=\"\u82b1\u82b1\u9171 LeetCode 1334. Find the City With the Smallest Number of Neighbors - \u5237\u9898\u627e\u5de5\u4f5c EP303\" width=\"500\" height=\"281\" src=\"https:\/\/www.youtube.com\/embed\/iE0tJ-8rPLQ?feature=oembed\" frameborder=\"0\" allow=\"accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture; web-share\" referrerpolicy=\"strict-origin-when-cross-origin\" allowfullscreen><\/iframe>\n<\/div><\/figure>\n\n\n\n<p>There are&nbsp;<code>n<\/code>&nbsp;cities numbered from&nbsp;<code>0<\/code>&nbsp;to&nbsp;<code>n-1<\/code>. Given the array&nbsp;<code>edges<\/code>&nbsp;where&nbsp;<code>edges[i] = [from<sub>i<\/sub>, to<sub>i<\/sub>, weight<sub>i<\/sub>]<\/code>&nbsp;represents a bidirectional and weighted edge between cities&nbsp;<code>from<sub>i<\/sub><\/code>&nbsp;and&nbsp;<code>to<sub>i<\/sub><\/code>, and given the integer&nbsp;<code>distanceThreshold<\/code>.<\/p>\n\n\n\n<p>Return the city with the smallest numberof&nbsp;cities that are reachable through some path and whose distance is&nbsp;<strong>at most<\/strong>&nbsp;<code>distanceThreshold<\/code>, If there are multiple such cities, return the city with the greatest number.<\/p>\n\n\n\n<p>Notice that the distance of a path connecting cities&nbsp;<em><strong>i<\/strong><\/em>&nbsp;and&nbsp;<em><strong>j<\/strong><\/em>&nbsp;is equal to the sum of the edges&#8217; weights along that path.<\/p>\n\n\n\n<p><strong>Example 1:<\/strong><\/p>\n\n\n\n<figure class=\"wp-block-image\"><img decoding=\"async\" src=\"https:\/\/assets.leetcode.com\/uploads\/2020\/01\/16\/find_the_city_01.png\" alt=\"\"\/><\/figure>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> n = 4, edges = [[0,1,3],[1,2,1],[1,3,4],[2,3,1]], distanceThreshold = 4\n<strong>Output:<\/strong> 3\n<strong>Explanation: <\/strong>The figure above describes the graph.&nbsp;\nThe neighboring cities at a distanceThreshold = 4 for each city are:\nCity 0 -&gt; [City 1, City 2]&nbsp;\nCity 1 -&gt; [City 0, City 2, City 3]&nbsp;\nCity 2 -&gt; [City 0, City 1, City 3]&nbsp;\nCity 3 -&gt; [City 1, City 2]&nbsp;\nCities 0 and 3 have 2 neighboring cities at a distanceThreshold = 4, but we have to return city 3 since it has the greatest number.\n<\/pre>\n\n\n\n<p><strong>Example 2:<\/strong><\/p>\n\n\n\n<figure class=\"wp-block-image\"><img decoding=\"async\" src=\"https:\/\/assets.leetcode.com\/uploads\/2020\/01\/16\/find_the_city_02.png\" alt=\"\"\/><\/figure>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> n = 5, edges = [[0,1,2],[0,4,8],[1,2,3],[1,4,2],[2,3,1],[3,4,1]], distanceThreshold = 2\n<strong>Output:<\/strong> 0\n<strong>Explanation: <\/strong>The figure above describes the graph.&nbsp;\nThe neighboring cities at a distanceThreshold = 2 for each city are:\nCity 0 -&gt; [City 1]&nbsp;\nCity 1 -&gt; [City 0, City 4]&nbsp;\nCity 2 -&gt; [City 3, City 4]&nbsp;\nCity 3 -&gt; [City 2, City 4]\nCity 4 -&gt; [City 1, City 2, City 3]&nbsp;\nThe city 0 has 1 neighboring city at a distanceThreshold = 2.\n<\/pre>\n\n\n\n<p><strong>Constraints:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\"><li><code>2 &lt;= n &lt;= 100<\/code><\/li><li><code>1 &lt;= edges.length &lt;= n * (n - 1) \/ 2<\/code><\/li><li><code>edges[i].length == 3<\/code><\/li><li><code>0 &lt;= from<sub>i<\/sub>&nbsp;&lt; to<sub>i<\/sub>&nbsp;&lt; n<\/code><\/li><li><code>1 &lt;= weight<sub>i<\/sub>,&nbsp;distanceThreshold &lt;= 10^4<\/code><\/li><li>All pairs&nbsp;<code>(from<sub>i<\/sub>, to<sub>i<\/sub>)<\/code>&nbsp;are distinct.<\/li><\/ul>\n\n\n\n<figure class=\"wp-block-image\"><img loading=\"lazy\" decoding=\"async\" width=\"960\" height=\"540\" src=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/01\/1334-ep303-1.png\" alt=\"\" class=\"wp-image-6163\" srcset=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/01\/1334-ep303-1.png 960w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/01\/1334-ep303-1-300x169.png 300w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/01\/1334-ep303-1-768x432.png 768w\" sizes=\"auto, (max-width: 960px) 100vw, 960px\" \/><\/figure>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solution1: Floyd-Warshall<\/strong><\/h2>\n\n\n\n<p>All pair shortest path<\/p>\n\n\n\n<p>Time complexity: O(n^3)<br>Space complexity: O(n^2)<\/p>\n\n\n\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">C++<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"C++\">\n\/\/ Author: Huahua\nclass Solution {\npublic:\n  int findTheCity(int n, vector<vector<int>>& edges, int distanceThreshold) {\n    vector<vector<int>> dp(n, vector<int>(n, INT_MAX \/ 2));\n    for (const auto& e : edges)      \n      dp[e[0]][e[1]] = dp[e[1]][e[0]] = e[2];    \n    \n    for (int k = 0; k < n; ++k)\n      for (int u = 0; u < n; ++u)\n        for (int v = 0; v < n; ++v)\n          dp[u][v] = min(dp[u][v], dp[u][k] + dp[k][v]);\n    \n    int ans = -1;\n    int min_nb = INT_MAX;\n    for (int u = 0; u < n; ++u) {\n      int nb = 0;\n      for (int v = 0; v < n; ++v)\n        if (v != u &#038;&#038; dp[u][v] <= distanceThreshold)\n          ++nb;\n      if (nb <= min_nb) {\n        min_nb = nb;\n        ans = u;\n      }\n    }\n    \n    return ans;\n  }\n};\n<\/pre>\n<\/div><\/div>\n\n\n\n<p><strong>Solution 2: Dijkstra's Algorithm<\/strong><\/p>\n\n\n\n<p>Time complexity: O(V * ElogV) \/ worst O(n^3*logn), best O(n^2*logn)<br>Space complexity: O(V + E)<\/p>\n\n\n\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">C++<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"C++\">\n\/\/ Author: Huahua\n\/\/ Author: Huahua\nclass Solution {\npublic:\n  int findTheCity(int n, vector<vector<int>>& edges, int t) {\n    vector<vector<pair<int, int>>> g(n);\n    for (const auto& e : edges) {\n      g[e[0]].emplace_back(e[1], e[2]);\n      g[e[1]].emplace_back(e[0], e[2]);\n    }\n    \n    \/\/ Returns the number of nodes within t from s.\n    auto dijkstra = [&](int s) {\n      vector<int> dist(n, INT_MAX \/ 2);\n      set<pair<int, int>> q; \/\/ <dist, node>\n      vector<set<pair<int, int>>::const_iterator> its(n);\n      dist[s] = 0;\n      for (int i = 0; i < n; ++i)\n        its[i] = q.emplace(dist[i], i).first;\n      while (!q.empty()) {\n        auto it = cbegin(q);\n        int d = it->first;\n        int u = it->second;\n        q.erase(it);        \n        if (d > t) break; \/\/ pruning\n        for (const auto& p : g[u]) {\n          int v = p.first;\n          int w = p.second;\n          if (dist[v] <= d + w) continue;\n          \/\/ Decrease key\n          q.erase(its[v]);\n          its[v] = q.emplace(dist[v] = d + w, v).first;\n        }\n      }\n      return count_if(begin(dist), end(dist), [t](int d) { return d <= t; });\n    };\n    \n    int ans = -1;\n    int min_nb = INT_MAX;\n    for (int i = 0; i < n; ++i) {\n      int nb = dijkstra(i);\n      if (nb <= min_nb) {\n        min_nb = nb;\n        ans = i;\n      }\n    }\n    \n    return ans;\n  }\n};\n\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"<p>There are&nbsp;n&nbsp;cities numbered from&nbsp;0&nbsp;to&nbsp;n-1. Given the array&nbsp;edges&nbsp;where&nbsp;edges[i] = [fromi, toi, weighti]&nbsp;represents a bidirectional and weighted edge between cities&nbsp;fromi&nbsp;and&nbsp;toi, and given the integer&nbsp;distanceThreshold. Return the city&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[76],"tags":[540,18,538,77,177,398,87],"class_list":["post-6149","post","type-post","status-publish","format-standard","hentry","category-graph","tag-dijkstra","tag-dp","tag-floyd-warshall","tag-graph","tag-medium","tag-on3","tag-shortest-path","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/6149","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=6149"}],"version-history":[{"count":6,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/6149\/revisions"}],"predecessor-version":[{"id":6164,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/6149\/revisions\/6164"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=6149"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=6149"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=6149"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}