{"id":122,"date":"2023-04-11T20:34:18","date_gmt":"2023-04-11T12:34:18","guid":{"rendered":"http:\/\/120.55.184.7\/?p=122"},"modified":"2025-04-16T00:44:23","modified_gmt":"2025-04-15T16:44:23","slug":"leetcode-2473-%e8%b4%ad%e4%b9%b0%e8%8b%b9%e6%9e%9c%e7%9a%84%e6%9c%80%e4%bd%8e%e6%88%90%e6%9c%ac","status":"publish","type":"post","link":"https:\/\/beijian99.top\/?p=122","title":{"rendered":"leetcode 2473 \u8d2d\u4e70\u82f9\u679c\u7684\u6700\u4f4e\u6210\u672c"},"content":{"rendered":"\n<figure class=\"wp-block-image size-full\"><img loading=\"lazy\" decoding=\"async\" width=\"905\" height=\"468\" src=\"http:\/\/120.55.184.7\/wp-content\/uploads\/2025\/04\/image-4.png\" alt=\"\" class=\"wp-image-123\" srcset=\"https:\/\/beijian99.top\/wp-content\/uploads\/2025\/04\/image-4.png 905w, https:\/\/beijian99.top\/wp-content\/uploads\/2025\/04\/image-4-300x155.png 300w, https:\/\/beijian99.top\/wp-content\/uploads\/2025\/04\/image-4-768x397.png 768w\" sizes=\"auto, (max-width: 905px) 100vw, 905px\" \/><\/figure>\n\n\n\n<figure class=\"wp-block-image size-full\"><img loading=\"lazy\" decoding=\"async\" width=\"904\" height=\"749\" src=\"http:\/\/120.55.184.7\/wp-content\/uploads\/2025\/04\/image-5.png\" alt=\"\" class=\"wp-image-124\" srcset=\"https:\/\/beijian99.top\/wp-content\/uploads\/2025\/04\/image-5.png 904w, https:\/\/beijian99.top\/wp-content\/uploads\/2025\/04\/image-5-300x249.png 300w, https:\/\/beijian99.top\/wp-content\/uploads\/2025\/04\/image-5-768x636.png 768w\" sizes=\"auto, (max-width: 904px) 100vw, 904px\" \/><\/figure>\n\n\n\n<figure class=\"wp-block-image size-full\"><img loading=\"lazy\" decoding=\"async\" width=\"877\" height=\"766\" src=\"http:\/\/120.55.184.7\/wp-content\/uploads\/2025\/04\/image-6.png\" alt=\"\" class=\"wp-image-125\" srcset=\"https:\/\/beijian99.top\/wp-content\/uploads\/2025\/04\/image-6.png 877w, https:\/\/beijian99.top\/wp-content\/uploads\/2025\/04\/image-6-300x262.png 300w, https:\/\/beijian99.top\/wp-content\/uploads\/2025\/04\/image-6-768x671.png 768w\" sizes=\"auto, (max-width: 877px) 100vw, 877px\" \/><\/figure>\n\n\n\n<figure class=\"wp-block-image size-full\"><img loading=\"lazy\" decoding=\"async\" width=\"914\" height=\"316\" src=\"http:\/\/120.55.184.7\/wp-content\/uploads\/2025\/04\/image-7.png\" alt=\"\" class=\"wp-image-126\" srcset=\"https:\/\/beijian99.top\/wp-content\/uploads\/2025\/04\/image-7.png 914w, https:\/\/beijian99.top\/wp-content\/uploads\/2025\/04\/image-7-300x104.png 300w, https:\/\/beijian99.top\/wp-content\/uploads\/2025\/04\/image-7-768x266.png 768w\" sizes=\"auto, (max-width: 914px) 100vw, 914px\" \/><\/figure>\n\n\n\n<p>\u89e3\u9898\u601d\u8def<br>\u4eceA\u70b9\u51fa\u53d1\uff0c\u5230B\u70b9\u4e70\u82f9\u679c\uff0c\u7136\u540e\u56de\u5230A\u70b9\uff0c\u8981\u6c42\u627e\u5230\u6700\u5c0f\u82b1\u8d39\u3002\u5148\u4e0d\u8003\u8651\u4e70\u5b8c\u82f9\u679c\u4e4b\u540e\u7684\u6210\u672c\u8981\u4e58\u4e0a\u56e0\u5b50K\u8fd9\u4e00\u9650\u5236\uff0c\u7136\u540e\u8d2a\u5fc3\u5730\u8003\u8651\u4e00\u4e0b\uff0cA-&gt;B \u548c B-&gt;A \u6765\u56de\u90fd\u9009\u62e9\u6700\u77ed\u8def\u624d\u662f\u6700\u4f18\u7684\uff0c\u800c\u6700\u77ed\u8def\u7684\u82b1\u8d39\u662f\u552f\u4e00\u786e\u5b9a\u7684\uff0c\u6240\u4ee5\u6765\u56de\u7684\u82b1\u8d39\u662f\u4e00\u6837\u7684\uff0c\u90a3\u4e48\u603b\u82b1\u8d39\u662f2\u500d\u7684\u6700\u77ed\u8def\u3002\u6b64\u65f6\u518d\u8003\u8651\u56e0\u5b50K\uff0c\u4e70\u5b8c\u82f9\u679c\u4e4b\u540e\uff0c\u56e0\u5b50K\u5bf9\u6240\u6709\u8def\u5f84\u751f\u6548\uff0c\u6240\u4ee5\u867d\u7136\u6700\u77ed\u8def\u53d8\u8d35\u4e86\uff0c\u4f46\u5176\u5b83\u7684\u8def\u53ea\u4f1a\u66f4\u8d35\uff0c\u6700\u77ed\u8def\u8fd8\u662f\u201c\u90a3\u6761\u8def\u5f84\u201d\uff0c\u56e0\u5b50K\u5e76\u4e0d\u5f71\u54cd\u201c\u8be5\u600e\u4e48\u8d70\u201d\uff0c\u53ea\u662f\u8def\u8d39\u8981\u6574\u4e2a\u4e58\u4e0ak\u3002\u5047\u8bbeA-&gt;B \u6700\u77ed\u8def\u7684\u82b1\u8d39\u662f cost,\u90a3\u4e48 B-&gt;A \u6309\u7167\u6700\u77ed\u8def\u539f\u8def\u8fd4\u56de\uff0c\u82b1\u8d39\u4e3a cost * k ,\u90a3\u4e48\u6765\u56de\u7684\u603b\u82b1\u8d39\u4e3a cost * (k+1).<\/p>\n\n\n\n<p>\u4ee5A\u4e3a\u6e90\u70b9\uff0c\u6c42\u89e3\u5355\u6e90\u6700\u77ed\u8def\uff0c\u7136\u540e\u679a\u4e3eB\u70b9\uff08\u4e5f\u5c31\u662f\u4e70\u82f9\u679c\u7684\u70b9\uff09\uff0cmin(dist(A,B)+appleCost(B) ) \u5373\u4e3aanser[A] ,\u4f46\u9898\u76ee\u8981\u6c42\u6240\u6709\u7684anser\uff0c\u90a3\u4e48\u8fd8\u9700\u8981\u679a\u4e3eA\u70b9\u4f5c\u4e3a\u6e90\u70b9\uff0c\u4f9d\u6b21\u6c42\u89e3anser[A]\u3002\u65f6\u95f4\u590d\u6742\u5ea6\u4e3a (n<sup>2<\/sup> log <sup>n<\/sup>) .<\/p>\n\n\n\n<p>\u8003\u8651\u4f18\u5316\u4e00\u4e0b\uff0c\u5efa\u7acb\u4e00\u4e2a\u865a\u62df\u6e90\u70b9 X\uff0cX\u4e0e\u4efb\u610f\u57ce\u5e02\u4e4b\u95f4\u90fd\u6709\u4e00\u6761\u8def\uff0c\u82b1\u8d39\u4e3a\u5728\u76ee\u6807\u57ce\u5e02\u4e70\u82f9\u679c\u7684\u6210\u672c\u3002\u90a3\u4e48\u9898\u610f\u5c31\u53ef\u4ee5\u8f6c\u5316\u4e00\u4e0b\uff0c\u53d8\u6210\u6c42\u4ece\u6e90\u70b9X\u5f00\u59cb\uff0c\u5230\u4efb\u610f\u57ce\u5e02\u7684\u6700\u77ed\u8def\uff08\u4e58\u4e0a(k+1)\uff09\u3002\u6b64\u65f6\u53ea\u9700\u8981\u7528Dijkstra\u6c42\u89e3\u4e00\u6b21\u5373\u53ef\uff0c\u65f6\u95f4\u590d\u6742\u5ea6\u4e3a N*log<sup>N<\/sup> \u3002<br>\u2014\u2014\u2014\u2014\u2014\u2014\u2014\u2014\u2014\u2014\u2014\u2014\u2014\u2014\u2014\u2014<\/p>\n\n\n<div class=\"wp-block-syntaxhighlighter-code \"><pre class=\"brush: cpp; gutter: true; title: ; notranslate\" title=\"\">\nclass Solution {\npublic:\n    vector&lt;long long&gt; minCost(int n, vector&lt;vector&lt;int&gt;&gt;&amp; roads, vector&lt;int&gt;&amp; appleCost, int k) {\n        vector&lt;vector&lt;pair&lt;int,int&gt;&gt;&gt;G(n+1);\n        for(auto &amp;road:roads){\n            int &amp;a=road&#x5B;0],&amp;b=road&#x5B;1],cost=road&#x5B;2]*(k+1);\n            G&#x5B;a].emplace_back(b,cost);\n            G&#x5B;b].emplace_back(a,cost);\n        }\n        vector&lt;long long&gt;dis(n+1);\n        vector&lt;int&gt;vis(n+1);\n        auto cmp=&#x5B;](pair&lt;int,int&gt;&amp;a,pair&lt;int,int&gt;&amp;b){\n            return a.second&gt;b.second;\n        };\n        priority_queue&lt;pair&lt;int,int&gt;,vector&lt;pair&lt;int,int&gt;&gt;,decltype(cmp)&gt;q(cmp);\n        for(int i=1;i&lt;=n;i++){\n            dis&#x5B;i]=appleCost&#x5B;i-1];\n            q.emplace(i,dis&#x5B;i]);\n        }\n        while(!q.empty()){\n            int u=q.top().first;\n            q.pop();\n            if(vis&#x5B;u])continue;\n            vis&#x5B;u]=true;\n            for(auto &amp;&#x5B;v,cost]:G&#x5B;u]){\n                if(dis&#x5B;v]&gt;dis&#x5B;u]+cost){\n                    dis&#x5B;v]=dis&#x5B;u]+cost;\n                    q.emplace(v,dis&#x5B;v]);\n                }\n            }\n        } \n        dis.erase(dis.begin());\n        return dis;\n    }\n};\n<\/pre><\/div>","protected":false},"excerpt":{"rendered":"<p>\u89e3\u9898\u601d\u8def\u4eceA\u70b9\u51fa\u53d1\uff0c\u5230B\u70b9\u4e70\u82f9\u679c\uff0c\u7136\u540e\u56de\u5230A\u70b9\uff0c\u8981\u6c42\u627e\u5230\u6700\u5c0f\u82b1\u8d39\u3002\u5148\u4e0d\u8003\u8651\u4e70\u5b8c\u82f9\u679c\u4e4b\u540e\u7684\u6210\u672c\u8981\u4e58\u4e0a\u56e0\u5b50K\u8fd9\u4e00\u9650 [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"site-sidebar-layout":"default","site-content-layout":"","ast-site-content-layout":"","site-content-style":"default","site-sidebar-style":"default","ast-global-header-display":"","ast-banner-title-visibility":"","ast-main-header-display":"","ast-hfb-above-header-display":"","ast-hfb-below-header-display":"","ast-hfb-mobile-header-display":"","site-post-title":"","ast-breadcrumbs-content":"","ast-featured-img":"","footer-sml-layout":"","theme-transparent-header-meta":"","adv-header-id-meta":"","stick-header-meta":"","header-above-stick-meta":"","header-main-stick-meta":"","header-below-stick-meta":"","astra-migrate-meta-layouts":"default","ast-page-background-enabled":"default","ast-page-background-meta":{"desktop":{"background-color":"var(--ast-global-color-5)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"tablet":{"background-color":"","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"mobile":{"background-color":"","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""}},"ast-content-background-meta":{"desktop":{"background-color":"var(--ast-global-color-4)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"tablet":{"background-color":"var(--ast-global-color-4)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"mobile":{"background-color":"var(--ast-global-color-4)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""}},"footnotes":""},"categories":[4],"tags":[116],"class_list":["post-122","post","type-post","status-publish","format-standard","hentry","category-algorithm","tag-116"],"_links":{"self":[{"href":"https:\/\/beijian99.top\/index.php?rest_route=\/wp\/v2\/posts\/122","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/beijian99.top\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/beijian99.top\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/beijian99.top\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/beijian99.top\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=122"}],"version-history":[{"count":6,"href":"https:\/\/beijian99.top\/index.php?rest_route=\/wp\/v2\/posts\/122\/revisions"}],"predecessor-version":[{"id":140,"href":"https:\/\/beijian99.top\/index.php?rest_route=\/wp\/v2\/posts\/122\/revisions\/140"}],"wp:attachment":[{"href":"https:\/\/beijian99.top\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=122"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/beijian99.top\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=122"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/beijian99.top\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=122"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}