{"id":2314,"date":"2025-02-10T11:18:39","date_gmt":"2025-02-10T03:18:39","guid":{"rendered":"https:\/\/guapicoding.com\/?p=2314"},"modified":"2025-03-03T22:16:01","modified_gmt":"2025-03-03T14:16:01","slug":"%e5%8a%9b%e6%89%a3%e9%a2%98%e8%ae%b0%e4%b9%8b%e5%9b%be%e8%ae%ba","status":"publish","type":"post","link":"https:\/\/guapicoding.com\/?p=2314","title":{"rendered":"\u5361\u7801\u9898\u8bb0\u4e4b\u56fe\u8bba"},"content":{"rendered":"\n<p class=\"has-text-align-center\"><em><strong>More content<\/strong><\/em><strong><em>\uff1a<\/em><\/strong><a href=\"http:\/\/114.55.108.251\/?p=1744\" data-type=\"post\" data-id=\"1744\">LeetCode <\/a><a href=\"https:\/\/guapicoding.com\/?p=2315\" data-type=\"post\" data-id=\"1744\">hot100<\/a><a href=\"http:\/\/114.55.108.251\/?p=1744\" data-type=\"post\" data-id=\"1744\">@\u56fe\u8bba<\/a><\/p>\n\n\n\n<h2 class=\"wp-block-heading\">\u5927\u7eb2 <\/h2>\n\n\n\n<ul class=\"wp-block-list\">\n<li>\u6df1\u641c\u4e0e\u5e7f\u641c<\/li>\n\n\n\n<li>\u5e76\u67e5\u96c6<\/li>\n\n\n\n<li>\u6700\u5c0f\u751f\u6210\u6811\n<ul class=\"wp-block-list\">\n<li>Kruskal<\/li>\n\n\n\n<li>prim<\/li>\n<\/ul>\n<\/li>\n\n\n\n<li>\u62d3\u6251\u6392\u5e8f<\/li>\n\n\n\n<li>\u6700\u77ed\u8def\u7b97\u6cd5\n<ul class=\"wp-block-list\">\n<li>dijkstra(\u5355\u6e90)<\/li>\n\n\n\n<li>Bellman_ford(\u5355\u6e90&amp;\u8d1f\u6743)<\/li>\n\n\n\n<li>Floyd(\u591a\u6e90)<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n\n\n\n<h2 class=\"wp-block-heading\">\u4ee3\u7801\u6846\u67b6 <\/h2>\n\n\n\n<h4 class=\"wp-block-heading\">dfs<\/h4>\n\n\n\n<pre class=\"wp-block-code\"><code>vector&lt;vector&lt;int&gt;&gt; result; \/\/ \u4fdd\u5b58\u7b26\u5408\u6761\u4ef6\u7684\u6240\u6709\u8def\u5f84\nvector&lt;int&gt; path; \/\/ \u8d77\u70b9\u5230\u7ec8\u70b9\u7684\u8def\u5f84\nvoid dfs(\u53c2\u6570) {\n    if (\u7ec8\u6b62\u6761\u4ef6) {\n        \u5b58\u653e\u7ed3\u679c;\n        return;\n    }\n\n    for (\u9009\u62e9\uff1a\u672c\u8282\u70b9\u6240\u8fde\u63a5\u7684\u5176\u4ed6\u8282\u70b9) {\n        \u5904\u7406\u8282\u70b9;\n        dfs(\u56fe\uff0c\u9009\u62e9\u7684\u8282\u70b9); \/\/ \u9012\u5f52\n        \u56de\u6eaf\uff0c\u64a4\u9500\u5904\u7406\u7ed3\u679c\n    }\n}<\/code><\/pre>\n\n\n\n<h4 class=\"wp-block-heading\">bfs<\/h4>\n\n\n\n<pre class=\"wp-block-code\"><code>int dir&#91;4]&#91;2] = {0, 1, 1, 0, -1, 0, 0, -1}; \/\/ \u8868\u793a\u56db\u4e2a\u65b9\u5411\n\/\/ grid \u662f\u5730\u56fe\uff0c\u4e5f\u5c31\u662f\u4e00\u4e2a\u4e8c\u7ef4\u6570\u7ec4\n\/\/ visited\u6807\u8bb0\u8bbf\u95ee\u8fc7\u7684\u8282\u70b9\uff0c\u4e0d\u8981\u91cd\u590d\u8bbf\u95ee\n\/\/ x,y \u8868\u793a\u5f00\u59cb\u641c\u7d22\u8282\u70b9\u7684\u4e0b\u6807\nvoid bfs(vector&lt;vector&lt;char&gt;&gt;&amp; grid, vector&lt;vector&lt;bool&gt;&gt;&amp; visited, int x, int y) {\n    queue&lt;pair&lt;int, int&gt;&gt; que; \/\/ \u5b9a\u4e49\u961f\u5217\n    que.push({x, y}); \/\/ \u8d77\u59cb\u8282\u70b9\u52a0\u5165\u961f\u5217\n    visited&#91;x]&#91;y] = true; \/\/ \u53ea\u8981\u52a0\u5165\u961f\u5217\uff0c\u7acb\u523b\u6807\u8bb0\u4e3a\u8bbf\u95ee\u8fc7\u7684\u8282\u70b9\n    while(!que.empty()) { \/\/ \u5f00\u59cb\u904d\u5386\u961f\u5217\u91cc\u7684\u5143\u7d20\n        pair&lt;int ,int&gt; cur = que.front(); que.pop(); \/\/ \u4ece\u961f\u5217\u53d6\u5143\u7d20\n        int curx = cur.first;\n        int cury = cur.second; \/\/ \u5f53\u524d\u8282\u70b9\u5750\u6807\n        for (int i = 0; i &lt; 4; i++) { \/\/ \u5f00\u59cb\u60f3\u5f53\u524d\u8282\u70b9\u7684\u56db\u4e2a\u65b9\u5411\u5de6\u53f3\u4e0a\u4e0b\u53bb\u904d\u5386\n            int nextx = curx + dir&#91;i]&#91;0]; \/\/ \u83b7\u53d6\u5468\u8fb9\u56db\u4e2a\u65b9\u5411\u7684\u5750\u6807\n            int nexty = cury + dir&#91;i]&#91;1]; \/\/ \u6ce8\u610fx\u5e76\u4e0d\u662f\u6a2a\u5750\u6807\uff0c\u800c\u662f\u884c\u53f7\n            if (nextx &lt; 0 || nextx &gt;= grid.size() || nexty &lt; 0 || nexty &gt;= grid&#91;0].size()) continue;  \/\/ \u5750\u6807\u8d8a\u754c\u4e86\uff0c\u76f4\u63a5\u8df3\u8fc7\n            if (!visited&#91;nextx]&#91;nexty]) { \/\/ \u5982\u679c\u8282\u70b9\u6ca1\u88ab\u8bbf\u95ee\u8fc7\n                que.push({nextx, nexty});  \/\/ \u961f\u5217\u6dfb\u52a0\u8be5\u8282\u70b9\u4e3a\u4e0b\u4e00\u8f6e\u8981\u904d\u5386\u7684\u8282\u70b9\n                visited&#91;nextx]&#91;nexty] = true; \/\/ \u53ea\u8981\u52a0\u5165\u961f\u5217\u7acb\u523b\u6807\u8bb0\uff0c\u907f\u514d\u91cd\u590d\u8bbf\u95ee\n            }\n        }\n    }\n}<\/code><\/pre>\n\n\n\n<h4 class=\"wp-block-heading\">\u5e76\u67e5\u96c6<\/h4>\n\n\n\n<pre class=\"wp-block-code\"><code>vector&lt;int&gt; fa(n+1, 0); \/\/ n\u6839\u636e\u9898\u76ee\u4e2d\u8282\u70b9\u6570\u91cf\u800c\u5b9a\n\n\/\/ \u5e76\u67e5\u96c6\u521d\u59cb\u5316\nvoid init() {\n    for(int i = 1; i &lt;= n; i++) fa&#91;i] = i;\n}\n\n\/\/ \u5e76\u67e5\u96c6\u91cc\u5bfb\u6839\u7684\u8fc7\u7a0b\nint find(int x) {\n    if(fa&#91;x] == x) return x;\n    return fa&#91;x] = find(fa&#91;x]); \/\/\u8def\u5f84\u538b\u7f29\n}\n\n\/\/ \u5224\u65ad u \u548c v\u662f\u5426\u5c5e\u4e8e\u540c\u4e00\u4e2a\u6839\nbool isSame(int u, int v) {\n    int fu = find(u);\n    int fv = find(v);\n    return fu == fv;\n}\n\n\/\/ \u5c06v-&gt;u \u8fd9\u6761\u8fb9\u52a0\u5165\u5e76\u67e5\u96c6\nvoid merge(int u, int v) {\n    int fu = find(u);\n    int fv = find(v);\n    if(fu == fv) return ;\n    fa&#91;fv] = fu;\n}<\/code><\/pre>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h2 class=\"wp-block-heading\">\u6df1\u641c\u4e0e\u5e7f\u641c<\/h2>\n\n\n\n<h3 class=\"wp-block-heading\"><a href=\"https:\/\/kamacoder.com\/problempage.php?pid=1170\" target=\"_blank\" rel=\"noreferrer noopener\">98. \u6240\u6709\u53ef\u8fbe\u8def\u5f84<\/a>\u2705<\/h3>\n\n\n\n<p><strong><em>\u7b80\u5355\u7684dfs\u56de\u6eaf\uff0c\u56fe\u53ef\u4ee5\u7528\u90bb\u63a5\u77e9\u9635\u6216\u90bb\u63a5\u8868\u4e24\u79cd\u65b9\u5f0f\u5b9e\u73b0<\/em><\/strong><\/p>\n\n\n\n<p><strong><em>\u6ce8\u610f\u4e24\u79cd\u65b9\u5f0f\u7684\u521d\u59cb\u5316\u4e0d\u540c<\/em><\/strong><\/p>\n\n\n\n<p><strong>\u90bb\u63a5\u77e9\u9635\uff1a<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>#include&lt;bits\/stdc++.h&gt;\nusing namespace std;\n\nint n, m;\nvector&lt;vector&lt;int&gt;&gt; graph;\nvector&lt;vector&lt;int&gt;&gt; res;\nvector&lt;int&gt; path;\n\nvoid dfs(int cur) {\n    if(cur == n) {\n        res.push_back(path);\n    }\n    \n    for(int i = 0; i &lt; n; i++) {\n        if(!graph&#91;cur-1]&#91;i]) continue;\n        path.push_back(i+1);\n        dfs(i+1);\n        path.pop_back(); \/\/\u56de\u6eaf\n    }\n    \n    return ;\n}\n\nint main() {\n    cin &gt;&gt; n &gt;&gt; m;\n    graph.resize(n, vector&lt;int&gt;(n, 0)); \/\/\u5916\u5c42\u548c\u5185\u5c42vector\u90fd\u8981\u521d\u59cb\u5316\n    int x, y;\n    for(int i = 0; i &lt; m; i++) {\n        cin &gt;&gt; x &gt;&gt; y; \n        graph&#91;x-1]&#91;y-1] = 1;\n    }\n    \n    \/\/ for(int i = 0; i &lt; n; i++) {\n    \/\/     for(int j = 0; j &lt; n; j++) {\n    \/\/         cout &lt;&lt; graph&#91;i]&#91;j] &lt;&lt; \" \";\n    \/\/     }\n    \/\/     cout &lt;&lt; endl;\n    \/\/ }\n    \n    path.push_back(1);\n    dfs(1);\n    \n    if(!res.size()) {\n        cout &lt;&lt; -1;\n        return 0;\n    }\n    \n    for(int i = 0; i &lt; res.size(); i++) {\n        for(int j = 0; j &lt; res&#91;i].size() - 1; j++) {\n            cout &lt;&lt; res&#91;i]&#91;j] &lt;&lt; \" \";\n        }\n        cout &lt;&lt; res&#91;i]&#91;res&#91;i].size() - 1] &lt;&lt; endl;\n    }\n    \n    return 0;\n}<\/code><\/pre>\n\n\n\n<p><strong>\u90bb\u63a5\u8868\uff1a<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>#include&lt;bits\/stdc++.h&gt;\nusing namespace std;\n\nint n, m;\nvector&lt;list&lt;int&gt;&gt; graph;\nvector&lt;vector&lt;int&gt;&gt; res;\nvector&lt;int&gt; path;\n\nvoid dfs(int cur) {\n    if(cur == n) {\n        res.push_back(path);\n        return ;\n    }\n    \n    for(int i : graph&#91;cur-1]) {\n        path.push_back(i);\n        dfs(i);\n        path.pop_back(); \/\/\u56de\u6eaf\n    }\n    \n    return ;\n}\n\nint main() {\n    cin &gt;&gt; n &gt;&gt; m;\n    graph.resize(n); \/\/\u53ea\u9700\u521d\u59cb\u5316\u5916\u5c42vector\uff0c\u5185\u5c42list\u672c\u6765\u5c31\u662f\u52a8\u6001\u7684\n\n    int x, y;\n    for(int i = 0; i &lt; m; i++) {\n        cin &gt;&gt; x &gt;&gt; y; \n        graph&#91;x-1].push_back(y);\n    }\n    \n    \/\/ for(int i = 0; i &lt; n; i++) {\n    \/\/     for(int j = 0; j &lt; graph&#91;i].size(); j++) {\n    \/\/         cout &lt;&lt; graph&#91;i]&#91;j] &lt;&lt; \" \";\n    \/\/     }\n    \/\/     cout &lt;&lt; endl;\n    \/\/ }\n    \n    path.push_back(1);\n    dfs(1);\n    \n    if(!res.size()) {\n        cout &lt;&lt; -1;\n        return 0;\n    }\n    \n    for(int i = 0; i &lt; res.size(); i++) {\n        for(int j = 0; j &lt; res&#91;i].size() - 1; j++) {\n            cout &lt;&lt; res&#91;i]&#91;j] &lt;&lt; \" \";\n        }\n        cout &lt;&lt; res&#91;i]&#91;res&#91;i].size() - 1] &lt;&lt; endl;\n    }\n    \n    return 0;\n}<\/code><\/pre>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h3 class=\"wp-block-heading\"><a href=\"https:\/\/kamacoder.com\/problempage.php?pid=1171\">99. \u5c9b\u5c7f\u6570\u91cf<\/a>\u274c<\/h3>\n\n\n\n<p><strong><em>\u6838\u5fc3\u601d\u60f3\u662f\u6807\u8bb0\uff08\u7c7b\u4f3c\u5e76\u67e5\u96c6\uff09\uff0c\u6709d<\/em><\/strong><em style=\"font-weight: bold;\">fs\u548cbfs\u4e24\u79cd\u65b9\u6cd5<\/em><\/p>\n\n\n\n<p><strong><em>bfs\u8981\u6ce8\u610f\u53ea\u8981\u52a0\u5165\u961f\u5217\uff0c\u7acb\u5373\u6807\u8bb0\u8be5\u8282\u70b9\u8d70\u8fc7\uff0c\u5426\u5219\u4f1a\u91cd\u590d\u52a0\u5165\uff0c\u53ef\u80fd\u8d85\u65f6<\/em><\/strong><\/p>\n\n\n\n<p><strong>dfs\uff1a<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>#include&lt;bits\/stdc++.h&gt;\nusing namespace std;\n\nint n, m, res;\nint dir&#91;4]&#91;2] = {0, 1, 1, 0, -1, 0, 0, -1};\nvector&lt;vector&lt;int&gt;&gt; grid;\nvector&lt;vector&lt;bool&gt;&gt; visited;\n \nvoid dfs(int x, int y) { \/\/x\u662f\u884c\u53f7\uff0cy\u662f\u5217\u53f7\n    \/\/\u6ca1\u5199\u7ec8\u6b62\u6761\u4ef6\u662f\u56e0\u4e3a\u4e0b\u9762\u5faa\u73af\u91cc\u628a\u975e\u6cd5\u60c5\u51b5\u90fd\u6392\u9664\u4e86\n    for(int i = 0; i &lt; 4; i++) {\n        int nextx = x + dir&#91;i]&#91;0];\n        int nexty = y + dir&#91;i]&#91;1];\n        if(nextx &lt; 0 || nextx &gt;= n || nexty &lt; 0 || nexty &gt;= m) continue;\n        if(!visited&#91;nextx]&#91;nexty] &amp;&amp; grid&#91;nextx]&#91;nexty]) {\n            visited&#91;nextx]&#91;nexty] = true;\n            dfs(nextx, nexty);\n        }\n    }\n    \n}\n\nint main() {\n    cin &gt;&gt; n &gt;&gt; m;\n    \n    grid.resize(n, vector&lt;int&gt;(m));\n    visited.resize(n, vector&lt;bool&gt;(m, false));\n    for(int i = 0; i &lt; n; i++) {\n        for(int j = 0; j &lt; m; j++) {\n            cin &gt;&gt; grid&#91;i]&#91;j];\n        }\n    }\n    \n    for(int i = 0; i &lt; n; i++) {\n        for(int j = 0; j &lt; m; j++) {\n            if(!visited&#91;i]&#91;j] &amp;&amp; grid&#91;i]&#91;j]) {\n                res++;\n                visited&#91;i]&#91;j] = true;\n                dfs(i, j); \/\/\u628a\u4e0e\u4e4b\u76f8\u8fde\u7684\u9646\u5730\u90fd\u6807\u8bb0\u4e0a\u4f5c\u4e3a\u4e00\u4e2a\u6574\u4f53\n            }\n            \n        }\n    }\n    \n    cout &lt;&lt; res;\n    \n    return 0;\n    \n}<\/code><\/pre>\n\n\n\n<p><strong>bfs\uff1a<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>#include&lt;bits\/stdc++.h&gt;\nusing namespace std;\n\nint n, m, res;\nint dir&#91;4]&#91;2] = {0, 1, 1, 0, -1, 0, 0, -1};\nvector&lt;vector&lt;int&gt;&gt; grid;\nvector&lt;vector&lt;bool&gt;&gt; visited;\n\nvoid bfs(int x, int y) {\n    queue&lt;pair&lt;int, int&gt;&gt; q;\n    q.push({x, y});\n    visited&#91;x]&#91;y] = true;\n    while(!q.empty()) {\n        pair&lt;int, int&gt; cur = q.front();\n        q.pop();\n        int curx = cur.first;\n        int cury = cur.second;\n        for(int i = 0; i &lt; 4; i++) {\n            int nextx = curx + dir&#91;i]&#91;0];\n            int nexty = cury + dir&#91;i]&#91;1];\n            if(nextx &lt; 0 || nextx &gt;= n || nexty &lt; 0 || nexty &gt;= m) continue;\n            if(!visited&#91;nextx]&#91;nexty] &amp;&amp; grid&#91;nextx]&#91;nexty]) {\n                q.push({nextx, nexty});\n                visited&#91;nextx]&#91;nexty] = true;\n            }\n            \n        }    \n    }\n}\n\nint main() {\n    cin &gt;&gt; n &gt;&gt; m;\n    \n    grid.resize(n, vector&lt;int&gt;(m));\n    visited.resize(n, vector&lt;bool&gt;(m, false));\n    for(int i = 0; i &lt; n; i++) {\n        for(int j = 0; j &lt; m; j++) {\n            cin &gt;&gt; grid&#91;i]&#91;j];\n        }\n    }\n    \n    for(int i = 0; i &lt; n; i++) {\n        for(int j = 0; j &lt; m; j++) {\n            if(!visited&#91;i]&#91;j] &amp;&amp; grid&#91;i]&#91;j]) {\n                res++;\n                visited&#91;i]&#91;j] = true;\n                bfs(i, j); \/\/\u628a\u4e0e\u4e4b\u76f8\u8fde\u7684\u9646\u5730\u90fd\u6807\u8bb0\u4e0a\u4f5c\u4e3a\u4e00\u4e2a\u6574\u4f53\n            }\n            \n        }\n    }\n    \n    cout &lt;&lt; res;\n    \n    return 0;\n    \n}<\/code><\/pre>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h3 class=\"wp-block-heading\"><a href=\"https:\/\/kamacoder.com\/problempage.php?pid=1172\">100. \u5c9b\u5c7f\u7684\u6700\u5927\u9762\u79ef<\/a>\u2705<\/h3>\n\n\n\n<p><em><strong>\u8ddf<a href=\"https:\/\/kamacoder.com\/problempage.php?pid=1171\">99. \u5c9b\u5c7f\u6570\u91cf<\/a>\u5dee\u522b\u4e0d\u5927 \u641c\u7d22\u65f6\u52a0\u4e0a\u9762\u79ef\u8ba1\u6570\u5668\u5373\u53ef<\/strong><\/em><\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>#include&lt;bits\/stdc++.h&gt;\nusing namespace std;\n\nint n, m, res, area;\nint dir&#91;4]&#91;2] = {0, 1, 1, 0, 0, -1, -1, 0};\n\nvoid dfs(vector&lt;vector&lt;int&gt;&gt; &amp;grid, vector&lt;vector&lt;bool&gt;&gt; &amp;visited, int row, int col) {\n    for(int i = 0; i &lt; 4; i++) {\n        int nextx = row + dir&#91;i]&#91;0];\n        int nexty = col + dir&#91;i]&#91;1];\n        if(nextx &lt; 0 || nextx &gt;= n || nexty &lt; 0 || nexty &gt;= m) continue;\n        if(grid&#91;nextx]&#91;nexty] &amp;&amp; !visited&#91;nextx]&#91;nexty]) {\n            visited&#91;nextx]&#91;nexty] = true;\n            area++;\n            dfs(grid, visited, nextx, nexty);\n        }\n    }\n}\n\nint main() {\n    cin &gt;&gt; n &gt;&gt; m;\n    \n    vector&lt;vector&lt;int&gt;&gt; grid(n, vector&lt;int&gt;(m, 0));\n    vector&lt;vector&lt;bool&gt;&gt; visited(n, vector&lt;bool&gt;(m, false));\n    \n    for(int i = 0; i &lt; n; i++) {\n        for(int j = 0; j &lt; m; j++) {\n            cin &gt;&gt; grid&#91;i]&#91;j];\n        }\n    }\n    \n    for(int i = 0; i &lt; n; i++) {\n        for(int j = 0; j &lt; m; j++) {\n            if(grid&#91;i]&#91;j] &amp;&amp; !visited&#91;i]&#91;j]) {\n                area = 1;\n                visited&#91;i]&#91;j] = true;\n                \/\/dfs\u53ea\u5904\u7406\u4e0b\u4e00\u4e2a\u8282\u70b9\uff0c\u5373\u5728\u4e3b\u51fd\u6570\u9047\u5230\u5c9b\u5c7f\u5c31\u8ba1\u6570\u4e3a1\uff0cdfs\u5904\u7406\u63a5\u4e0b\u6765\u7684\u76f8\u90bb\u9646\u5730\n                dfs(grid, visited, i, j);\n                res = max(res, area);\n            }\n        }\n    }\n    \n    cout &lt;&lt; res &lt;&lt; endl;\n    \n    return 0;\n}<\/code><\/pre>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h3 class=\"wp-block-heading\"><br><a href=\"https:\/\/kamacoder.com\/problempage.php?pid=1173\">101. \u5b64\u5c9b\u7684\u603b\u9762\u79ef<\/a>\u274c<\/h3>\n\n\n\n<p><strong><em>\u8981\u627e\u5230\u4e0d\u9760\u8fb9\u7684\u9646\u5730\u9762\u79ef\uff0c\u53ea\u9700\u8981\u4ece\u5468\u8fb9\u9646\u5730\u5f00\u59cb\u5c06\u5468\u8fb9\u9760\u9646\u5730\u4e14\u76f8\u90bb\u7684\u9646\u5730\u90fd\u53d8\u6210\u6d77\u6d0b\uff0c\u7136\u540e\u518d\u91cd\u65b0\u904d\u5386\u5730\u56fe\u7edf\u8ba1\u6b64\u65f6\u8fd8\u5269\u4e0b\u7684\u9646\u5730\u5373\u53ef<\/em><\/strong><\/p>\n\n\n\n<p><strong><em>\u5373\u4f7f\u5728\u5c06\u5730\u56fe\u6539\u9020\u5b8c\u7edf\u8ba1\u5b64\u5c9b\u65f6\uff0c\u5728area++\u540e\u4e5f\u628a\u9646\u5730\u53d8\u6210\u4e86\u6d77\u6d0b\uff0c\u56e0\u6b64\u65e0\u9700visited\u6570\u7ec4\u6807\u8bb0\uff0c\u6839\u672c\u4e0d\u4f1a\u91cd\u590d\u8bbf\u95ee\uff08\u5df2\u7ecf\u53d8\u6210\u4e86\u6d77\u6d0b\uff09<\/em><\/strong><\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>#include&lt;bits\/stdc++.h&gt;\nusing namespace std;\n\nint n, m, res, area;\nint dir&#91;4]&#91;2] = {0, 1, 1, 0, 0, -1, -1, 0};\n\nvoid dfs(vector&lt;vector&lt;int&gt;&gt; &amp;grid, int row, int col) {\n    for(int i = 0; i &lt; 4; i++) {\n        int nextx = row + dir&#91;i]&#91;0];\n        int nexty = col + dir&#91;i]&#91;1];\n        if(nextx &lt; 0 || nextx &gt;= n || nexty &lt; 0 || nexty &gt;= m) continue;\n        if(grid&#91;nextx]&#91;nexty]) {\n            area++;\n            grid&#91;nextx]&#91;nexty] = 0;\n            dfs(grid, nextx, nexty);\n        }\n    }\n}\n\nint main() {\n    cin &gt;&gt; n &gt;&gt; m;\n    \n    vector&lt;vector&lt;int&gt;&gt; grid(n, vector&lt;int&gt;(m, 0));\n    vector&lt;vector&lt;bool&gt;&gt; visited(n, vector&lt;bool&gt;(m, false));\n    \n    for(int i = 0; i &lt; n; i++) {\n        for(int j = 0; j &lt; m; j++) {\n            cin &gt;&gt; grid&#91;i]&#91;j];\n        }\n    }\n    \n    \/\/\u4ece\u7b2c\u4e00\u5217\u548c\u6700\u540e\u4e00\u5217\u5411\u4e2d\u95f4\u904d\u5386\n    for(int i = 0; i &lt; n; i++) {\n        if(grid&#91;i]&#91;0]) {\n            grid&#91;i]&#91;0] = 0;\n            dfs(grid, i, 0);\n        }\n        if(grid&#91;i]&#91;m-1]) {\n            grid&#91;i]&#91;m-1] = 0;\n            dfs(grid, i, m-1);\n        }\n    }\n    \n    \/\/\u4ece\u7b2c\u4e00\u884c\u548c\u6700\u540e\u4e00\u884c\u5411\u4e2d\u95f4\u904d\u5386\n    for(int i = 0; i &lt; m; i++) {\n        if(grid&#91;0]&#91;i]) {\n            grid&#91;0]&#91;i] = 0;\n            dfs(grid, 0, i);\n        }\n        \n        if(grid&#91;n-1]&#91;i]) {\n            grid&#91;n-1]&#91;i] = 0;\n            dfs(grid, n-1, i);\n        }\n    }\n    \n    \/\/ for(int i = 0; i &lt; n; i++) {\n    \/\/     for(int j = 0; j &lt; m; j++) {\n    \/\/         cout &lt;&lt; grid&#91;i]&#91;j];\n    \/\/     }\n    \/\/     cout &lt;&lt; endl;\n    \/\/ }\n         \n    \n    for(int i = 0; i &lt; n; i++) {\n        for(int j = 0; j &lt; m; j++) {\n            if(grid&#91;i]&#91;j]) {\n                area = 1;\n                grid&#91;i]&#91;j] = 0;\n                dfs(grid, i, j);\n                \/\/ cout &lt;&lt; \"i = \" &lt;&lt; i &lt;&lt; \", j = \" &lt;&lt; j &lt;&lt; \", area = \" &lt;&lt; area &lt;&lt; endl;\n                res += area;\n            }\n        }\n    }\n    \n    cout &lt;&lt; res &lt;&lt; endl;\n    \n    return 0;\n}<\/code><\/pre>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h3 class=\"wp-block-heading\"><a href=\"https:\/\/kamacoder.com\/problempage.php?pid=1174\">102. \u6c89\u6ca1\u5b64\u5c9b<\/a>\u2705<\/h3>\n\n\n\n<p><em><strong>\u601d\u8def\u5f88\u7b80\u5355\uff1a<\/strong><\/em><em style=\"font-weight: bold;\">\u4e8b\u5148\u5907\u4efdgrid\uff0c\u5148\u4f7f\u7528\u4e0a\u9898<a href=\"https:\/\/kamacoder.com\/problempage.php?pid=1173\">101. \u5b64\u5c9b\u7684\u603b\u9762\u79ef<\/a>\u7684\u65b9\u6cd5\u628a\u5b64\u5c9b\u627e\u51fa\u6765\uff0c\u518d\u6839\u636e\u539f\u6570\u7ec4\u4e2d\u5b64\u5c9b\u7684\u4f4d\u7f6e\u5bf9<em style=\"font-weight: bold;\">\u5907\u4efd<\/em>\u8fdb\u884c\u4fee\u6539<\/em><\/p>\n\n\n\n<p><em><strong>\u8fd8\u6709\u4e00\u79cd\u601d\u8def\uff1a\u5148\u628a\u975e\u5b64\u5c9b\u6807\u8bb0\u4ece1\u6539\u4e3a2\uff0c\u6b64\u65f6\u5b64\u5c9b\u4e3a1\uff0c\u518d\u628a\u5b64\u5c9b\u4ece1\u6539\u4e3a0\uff08\u5373\u6c89\u6ca1\uff09\uff0c\u6700\u540e\u628a\u975e\u5b64\u5c9b\u6807\u8bb0\u4ece2\u518d\u6539\u56de1<\/strong><\/em><\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>#include&lt;bits\/stdc++.h&gt;\nusing namespace std;\n\nint n, m, res, area;\nint dir&#91;4]&#91;2] = {0, 1, 1, 0, 0, -1, -1, 0};\n\nvoid dfs(vector&lt;vector&lt;int&gt;&gt; &amp;grid, int row, int col) {\n    for(int i = 0; i &lt; 4; i++) {\n        int nextx = row + dir&#91;i]&#91;0];\n        int nexty = col + dir&#91;i]&#91;1];\n        if(nextx &lt; 0 || nextx &gt;= n || nexty &lt; 0 || nexty &gt;= m) continue;\n        if(grid&#91;nextx]&#91;nexty]) {\n            area++;\n            grid&#91;nextx]&#91;nexty] = 0;\n            dfs(grid, nextx, nexty);\n        }\n    }\n}\n\nint main() {\n    cin &gt;&gt; n &gt;&gt; m;\n    \n    vector&lt;vector&lt;int&gt;&gt; grid(n, vector&lt;int&gt;(m, 0));\n    vector&lt;vector&lt;int&gt;&gt; res(n, vector&lt;int&gt;(m, 0));\n    vector&lt;vector&lt;bool&gt;&gt; visited(n, vector&lt;bool&gt;(m, false));\n    \n    for(int i = 0; i &lt; n; i++) {\n        for(int j = 0; j &lt; m; j++) {\n            cin &gt;&gt; grid&#91;i]&#91;j];\n            res&#91;i]&#91;j] = grid&#91;i]&#91;j];\n        }\n    }\n    \n    \/\/\u4ece\u7b2c\u4e00\u5217\u548c\u6700\u540e\u4e00\u5217\u5411\u4e2d\u95f4\u904d\u5386\n    for(int i = 0; i &lt; n; i++) {\n        if(grid&#91;i]&#91;0]) {\n            grid&#91;i]&#91;0] = 0;\n            dfs(grid, i, 0);\n        }\n        if(grid&#91;i]&#91;m-1]) {\n            grid&#91;i]&#91;m-1] = 0;\n            dfs(grid, i, m-1);\n        }\n    }\n    \n    \/\/\u4ece\u7b2c\u4e00\u884c\u548c\u6700\u540e\u4e00\u884c\u5411\u4e2d\u95f4\u904d\u5386\n    for(int i = 0; i &lt; m; i++) {\n        if(grid&#91;0]&#91;i]) {\n            grid&#91;0]&#91;i] = 0;\n            dfs(grid, 0, i);\n        }\n        \n        if(grid&#91;n-1]&#91;i]) {\n            grid&#91;n-1]&#91;i] = 0;\n            dfs(grid, n-1, i);\n        }\n    }\n \n    \n    for(int i = 0; i &lt; n; i++) {\n        for(int j = 0; j &lt; m; j++) {\n            if(grid&#91;i]&#91;j]) res&#91;i]&#91;j] = 0;\n            \n            if(j == m) cout &lt;&lt; res&#91;i]&#91;j];\n            else cout &lt;&lt; res&#91;i]&#91;j] &lt;&lt; \" \";\n        }\n        cout &lt;&lt; endl;\n    }\n    \n    return 0;\n}<\/code><\/pre>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h3 class=\"wp-block-heading\"><a href=\"https:\/\/kamacoder.com\/problempage.php?pid=1175\">103. \u6c34\u6d41\u95ee\u9898<\/a>\u274c<\/h3>\n\n\n\n<p><strong><em>\u53ef\u4ee5\u76f4\u89c2\u60f3\u5230\uff1a\u904d\u5386\u6bcf\u4e2a\u70b9\uff0c\u770b\u8be5\u70b9\u80fd\u5426\u65e2\u5230\u8fbe\u5de6\u4e0a\u8fb9\u754c\uff0c\u4e5f\u80fd\u5230\u8fbe\u53f3\u4e0b\u8fb9\u754c\uff0c\u4f46\u8d85\u65f6\u4e86\uff08\u56e0\u4e3a\u904d\u5386\u662fn*m\uff0c\u6df1\u641c\u65f6\u4e5f\u662fn*m\uff09<\/em><\/strong><\/p>\n\n\n\n<p><em><strong>\u4ee5\u7a7a\u95f4\u6362\u65f6\u95f4\uff1a\u5b9a\u4e49\u4e24\u4e2a\u6570\u7ec4\uff0c\u5148\u4ece\u5de6\u4e0a\u8fb9\u754c\u5f00\u59cb\u9006\u6d41\u6807\u8bb0\uff0c\u518d\u4ece\u53f3\u4e0b\u8fb9\u754c\u9006\u6d41\u6807\u8bb0\uff0c\u88ab\u4e24\u4e2a\u6807\u8bb0\u90fd\u6807\u8bb0\u8fc7\u7684\u70b9\u5c31\u662f\u8981\u627e\u7684\u70b9<\/strong><\/em><\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>#include&lt;bits\/stdc++.h&gt;\nusing namespace std;\n\nint n, m;\nint dir&#91;4]&#91;2] = {0, 1, 1, 0, 0, -1, -1, 0};\n\nvoid dfs(vector&lt;vector&lt;int&gt;&gt; &amp;grid, vector&lt;vector&lt;bool&gt;&gt; &amp;visited, int row, int col) {\n    \n    for(int i = 0; i &lt; 4; i++) {\n        int nextx = row + dir&#91;i]&#91;0];\n        int nexty = col + dir&#91;i]&#91;1];\n        if(nextx &lt; 0 || nextx &gt;= n || nexty &lt; 0 || nexty &gt;= m) continue;\n        if(!visited&#91;nextx]&#91;nexty] &amp;&amp; grid&#91;row]&#91;col] &lt;= grid&#91;nextx]&#91;nexty]) {\n            visited&#91;nextx]&#91;nexty] = true;\n            dfs(grid, visited, nextx, nexty);\n        }\n    }\n \n}\n\nint main() {\n    cin &gt;&gt; n &gt;&gt; m;\n    vector&lt;vector&lt;int&gt;&gt; grid(n, vector&lt;int&gt;(m));\n    for(int i = 0; i &lt; n; i++) {\n        for(int j = 0; j &lt; m; j++) {\n            cin &gt;&gt; grid&#91;i]&#91;j];\n        }\n    } \n    \n    vector&lt;vector&lt;bool&gt;&gt; lu(n, vector&lt;bool&gt;(m, false));\n    vector&lt;vector&lt;bool&gt;&gt; rd(n, vector&lt;bool&gt;(m, false));\n    \n    for(int i = 0; i &lt; n; i++) {\n        lu&#91;i]&#91;0] = true;\n        dfs(grid, lu, i, 0); \/\/\u904d\u5386\u5de6\u8fb9\u754c\n        rd&#91;i]&#91;m-1] = true;\n        dfs(grid, rd, i, m-1); \/\/\u904d\u5386\u53f3\u8fb9\u754c\n    } \n    \n    for(int i = 0; i &lt; m; i++) {\n        lu&#91;0]&#91;i] = true;\n        dfs(grid, lu, 0, i); \/\/\u904d\u5386\u4e0a\u8fb9\u754c\n        rd&#91;n-1]&#91;i] = true;\n        dfs(grid, rd, n-1, i); \/\/\u904d\u5386\u4e0b\u8fb9\u754c\n    } \n    \n    for(int i = 0; i &lt; n; i++) {\n        for(int j = 0; j &lt; m; j++) {\n            if(lu&#91;i]&#91;j] &amp;&amp; rd&#91;i]&#91;j]) cout &lt;&lt; i &lt;&lt; \" \" &lt;&lt; j &lt;&lt; endl;\n        }\n    } \n    \n    return 0;\n}<\/code><\/pre>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h3 class=\"wp-block-heading\"><a href=\"https:\/\/kamacoder.com\/problempage.php?pid=1176\">104. \u5efa\u9020\u6700\u5927\u5c9b\u5c7f<\/a>\u274c<\/h3>\n\n\n\n<p><em><strong>\u4ece\u66b4\u529b\u5165\u624b\uff08\u904d\u5386\u5730\u56fe\uff0c\u5c1d\u8bd5\u5c06\u6bcf\u4e00\u4e2a0\u6539\u62101\uff0c\u7136\u540e\u53bb\u641c\u7d22\u5730\u56fe\u4e2d\u7684\u6700\u5927\u7684\u5c9b\u5c7f\u9762\u79ef\uff09\uff0c\u4f46\u662f\u8981\u4f18\u5316<\/strong><\/em><\/p>\n\n\n\n<p><em><strong>\u4e8b\u5148\u628a\u6bcf\u4e2a\u5c9b\u5c7f\u7684\u9762\u79ef\u8bb0\u5f55\u4e0b\u6765\uff08\u7528map\uff0ckey\u662f\u5c9b\u5c7f\u7f16\u53f7\uff0c\u628a\u8be5\u5c9b\u5c7f\u7684\u6bcf\u5757\u90fd\u6807\u8bb0\u4e3a\u6807\u53f7\uff0c\u4ece2\u5f00\u59cb\uff0cvalue\u662f\u9762\u79ef\uff09\uff0c\u5f53\u628a\u67d0\u57570\u53d8\u4e3a1\u540e\uff0c\u7edf\u8ba1\u5176\u5468\u8fb9\u8fde\u63a5\u7684\u5c9b\u5c7f\u4e4b\u548c<\/strong><\/em><\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>#include&lt;bits\/stdc++.h&gt;\nusing namespace std;\n\nint n, m;\nint id, cnt, area;\nint dir&#91;4]&#91;2] = {0, 1, 0, -1, 1, 0, -1, 0};\nunordered_map&lt;int, int&gt; mp; \/\/key:\u5c9b\u5c7f\u7f16\u53f7 value:\u5c9b\u5c7f\u9762\u79ef\n\nvoid dfs(vector&lt;vector&lt;int&gt;&gt; &amp;grid, vector&lt;vector&lt;bool&gt;&gt; &amp;visited, int row, int col) {\n    for(int i = 0; i &lt; 4; i++) {\n        int nextx = row + dir&#91;i]&#91;0];\n        int nexty = col + dir&#91;i]&#91;1];\n        if(nextx &lt; 0 || nextx &gt;= n || nexty &lt; 0 || nexty &gt;= m) continue;\n        if(grid&#91;nextx]&#91;nexty] &amp;&amp; !visited&#91;nextx]&#91;nexty]) {\n            visited&#91;nextx]&#91;nexty] = true;\n            grid&#91;nextx]&#91;nexty] = id;\n            cnt++;\n            dfs(grid, visited, nextx, nexty);\n        }\n    }\n}\n\nint main() {\n    cin &gt;&gt; n &gt;&gt; m;\n    vector&lt;vector&lt;int&gt;&gt; grid(n, vector&lt;int&gt;(m));\n    vector&lt;vector&lt;bool&gt;&gt; visited(n, vector&lt;bool&gt;(m, false));\n    for(int i = 0; i &lt; n; i++) {\n        for(int j = 0; j &lt; m; j++) {\n            cin &gt;&gt; grid&#91;i]&#91;j];\n        }\n    }\n    \n    bool is_allland = true;\n    \n    id = 2;\n    for(int i = 0; i &lt; n; i++) {\n        for(int j = 0; j &lt; m; j++) {\n            if(!grid&#91;i]&#91;j]) is_allland = false;\n            if(grid&#91;i]&#91;j] &amp;&amp; !visited&#91;i]&#91;j]) {\n                visited&#91;i]&#91;j] = true;\n                cnt = 1;\n                grid&#91;i]&#91;j] = id;\n                dfs(grid, visited, i, j);\n                mp.insert(make_pair(id++, cnt));\n            }\n        }\n    }\n    \n    if(is_allland) {\n        cout &lt;&lt; n * m &lt;&lt; endl;\n        return 0;\n    }\n    \n    \/\/ for(int i = 0; i &lt; n; i++) {\n    \/\/     for(int j = 0; j &lt; m; j++) {\n    \/\/         cout &lt;&lt; grid&#91;i]&#91;j] &lt;&lt; \" \";\n    \/\/     }\n    \/\/     cout &lt;&lt; endl;\n    \/\/ }\n    \n    \/\/ for(unordered_map&lt;int, int&gt;::iterator it = mp.begin(); it != mp.end(); it++)\n    \/\/     cout &lt;&lt; it-&gt;first &lt;&lt; \" \" &lt;&lt; it-&gt;second &lt;&lt; endl;\n    \n    int res = 0;\n    unordered_set&lt;int&gt; visited_island; \/\/\u8bb0\u5f55\u7d2f\u52a0\u8fc7\u7684\u5c9b\u5c7f\n    \n    for(int i = 0; i &lt; n; i++) {\n        for(int j = 0; j &lt; m; j++) {\n            if(!grid&#91;i]&#91;j]) {\n                visited_island.clear();\n                area = 1;\n                for(int k = 0; k &lt; 4; k++) {\n                    int nextx = i + dir&#91;k]&#91;0];\n                    int nexty = j + dir&#91;k]&#91;1];\n                    if(nextx &lt; 0 || nextx &gt;= n || nexty &lt; 0 || nexty &gt;= m) continue;\n                    if(visited_island.count(grid&#91;nextx]&#91;nexty])) continue; \/\/\u8bf4\u660e\u5df2\u7ecf\u52a0\u8fc7\u4e00\u6b21\u4e86\n                    \n                    area += mp&#91;grid&#91;nextx]&#91;nexty]];\n                    visited_island.insert(grid&#91;nextx]&#91;nexty]);\n                }\n                res = max(res, area);\n            }\n        }\n    }\n    \n    cout &lt;&lt; res &lt;&lt; endl;\n    \n    return 0;\n}<\/code><\/pre>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h3 class=\"wp-block-heading\"><a href=\"https:\/\/kamacoder.com\/problempage.php?pid=1183\">110. \u5b57\u7b26\u4e32\u63a5\u9f99<\/a>\u274c<\/h3>\n\n\n\n<p><em><strong>\u6ca1\u9886\u4f1a\u5230\u8fd9\u9898\u662f\u8ba9\u6c42\u6700\u77ed\u8def\u5f84\u7684\u957f\u5ea6\uff0c\u4e14\u4e0d\u7528\u627e\u51fa\u5177\u4f53\u8def\u5f84<\/strong><\/em><\/p>\n\n\n\n<p><em><strong>\u6700\u77ed\u8def\u5f84\u9002\u5408BFS\uff0c\u56e0\u4e3a\u5e7f\u641c\u53ea\u8981\u641c\u5230\u4e86\u7ec8\u70b9\uff0c\u90a3\u4e48\u4e00\u5b9a\u662f\u6700\u77ed\u7684\u8def\u5f84<\/strong><\/em><\/p>\n\n\n\n<p><em><strong>\u53ef\u4ee5\u5148\u6784\u5efa\u597d\u90bb\u63a5\u8868\uff0c\u65b9\u4fbfBFS<\/strong><\/em><\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>#include&lt;bits\/stdc++.h&gt;\nusing namespace std;\n\nstring beginStr, endStr;\nunordered_map&lt;string, vector&lt;string&gt;&gt; graph; \/\/\u90bb\u63a5\u8868\nunordered_map&lt;string, int&gt; visited; \/\/\u8bb0\u5f55\u5b57\u7b26\u4e32\uff0c\u9632\u6b62\u91cd\u590d\u641c, \u540c\u65f6\u8bb0\u5f55\u8def\u5f84\u957f\u5ea6 \n\nvoid buildGraph(vector&lt;string&gt; &amp;strs);\nint dif_letters(const string &amp;a, const string &amp;b);\nvoid bfs();\n\nvoid buildGraph(vector&lt;string&gt; &amp;strs) {\n    for(int i = 0; i &lt; strs.size(); i++) { \n        vector&lt;string&gt; v; \n        for(int j = 0; j &lt; strs.size(); j++) {\n            if(i == j) continue;\n            if(dif_letters(strs&#91;i], strs&#91;j]) == 1) {\n                v.push_back(strs&#91;j]);\n            }\n        }\n        graph.insert(make_pair(strs&#91;i], v));\n    }\n    \n    return ;\n}\n\nint dif_letters(const string &amp;a, const string &amp;b) {\n    int diff = 0;\n    for (int i = 0; i &lt; a.size(); i++) {\n        if (a&#91;i] != b&#91;i]) diff++;\n    }\n    return diff;\n}\n\nvoid bfs() {\n    queue&lt;string&gt; q;\n    q.push(beginStr);\n    visited.insert(make_pair(beginStr, 1));\n    while(!q.empty()) {\n        string node = q.front();\n        int path = visited&#91;node];\n        \/\/ cout &lt;&lt; \"node:\" &lt;&lt; node &lt;&lt; endl &lt;&lt; \"insert:\";\n        q.pop();\n        for(const auto &amp;s : graph&#91;node]) {\n            if(s == endStr) {\n                cout &lt;&lt; path+1 &lt;&lt; endl;\n                return ;\n            }\n            if(visited.count(s)) continue;\n            visited.insert(make_pair(s, path+1));\n            \/\/ cout &lt;&lt; s &lt;&lt; \" \";\n            q.push(s);\n        }\n    }\n}\n\nint main() {\n    int n;\n    cin &gt;&gt; n;\n    cin &gt;&gt; beginStr &gt;&gt; endStr;\n    vector&lt;string&gt; strs(n);\n    for(int i = 0; i &lt; n; i++) {\n        cin &gt;&gt; strs&#91;i];\n    }\n    strs.push_back(beginStr);\n    strs.push_back(endStr);\n    \n    \/\/graph(n+2, vector&lt;string&gt;(n+2));\n    \n    buildGraph(strs);\n    \n    \/\/ for(auto &amp;i : strs) cout &lt;&lt; i &lt;&lt; endl;\n    \n    \/\/ for(auto it = graph.begin(); it != graph.end(); ++it) {\n    \/\/     const auto&amp; front = it-&gt;first;\n    \/\/     const auto&amp; ss = it-&gt;second;\n    \/\/     cout &lt;&lt; front &lt;&lt; \": \";\n    \/\/     for(const auto &amp;s : ss) {\n    \/\/         cout &lt;&lt; s &lt;&lt; \" \";\n    \/\/     }\n    \/\/     cout &lt;&lt; endl;\n    \/\/ }\n    \n    bfs();\n    \n    return 0;\n}<\/code><\/pre>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h3 class=\"wp-block-heading\"><a href=\"https:\/\/kamacoder.com\/problempage.php?pid=1177\">105. \u6709\u5411\u56fe\u7684\u5b8c\u5168\u53ef\u8fbe\u6027<\/a>\u2705<\/h3>\n\n\n\n<p><em><strong>\u6784\u5efa\u90bb\u63a5\u8868+dfs<\/strong><\/em><\/p>\n\n\n\n<p><em><strong>visited\u6570\u7ec4\u5728\u6b64\u9898\u65e2\u6807\u8bb0\u662f\u5426\u8d70\u8fc7\uff08\u9632\u6b62\u6b7b\u5faa\u73af+\u4f18\u5316\uff09\uff0c\u53c8\u662f\u662f\u5426\u8fde\u901a\u7684\u4f9d\u636e<\/strong><\/em><\/p>\n\n\n\n<p><em><strong>\u6ce8\u610f\u6b64\u9898\u4e0d\u7528\u56de\u6eaf\uff0c\u56e0\u4e3a\u4e0d\u7528\u8c03\u5934\uff08\u53ea\u662f\u6d4b\u8bd5\u8fde\u901a\u6027\uff0c\u76f4\u63a5\u6807\u8bb0\u5c31\u597d\uff0c\u5982\u679c\u662f\u627e\u4e00\u6761\u53ef\u884c\u8def\u5f84\u5c31\u9700\u8981\u56de\u6eaf\u4e86\uff09<\/strong><\/em><\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>#include&lt;bits\/stdc++.h&gt;\nusing namespace std;\n \nint n, m;\nvector&lt;vector&lt;int&gt;&gt; graph; \/\/\u90bb\u63a5\u8868\nvector&lt;bool&gt; visited;  \n\nvoid buildGraph(vector&lt;pair&lt;int, int&gt;&gt; &amp;edges) {\n    for(int i = 0; i &lt; m; i++) { \n        graph&#91;edges&#91;i].first].push_back(edges&#91;i].second);\n    }\n    return ;\n}\n \nvoid dfs(int node) {\n    for(int i = 0; i &lt; graph&#91;node].size(); i++) {\n        if(visited&#91;graph&#91;node]&#91;i]]) continue;\n        visited&#91;graph&#91;node]&#91;i]] = true;\n        dfs(graph&#91;node]&#91;i]);\n    }\n    \n    return ;\n}\nint main() {\n    cin &gt;&gt; n &gt;&gt; m;\n    vector&lt;pair&lt;int, int&gt;&gt; edges;\n    int x, y;\n    for(int i = 0; i &lt; m; i++) {\n        cin &gt;&gt; x &gt;&gt; y;\n        edges.push_back(make_pair(x, y));\n    }\n    \n    graph.resize(n+1);  \n    buildGraph(edges);\n \n    visited.resize(n+1, false);\n    visited&#91;1] = true;\n    dfs(1);\n    \n    for(int i = 2; i &lt;= n; i++) {\n        if(visited&#91;i] == false) {\n            cout &lt;&lt; \"-1\" &lt;&lt; endl;\n            return 0;\n        }\n    }\n    cout &lt;&lt; \"1\" &lt;&lt; endl;\n\n    return 0;\n}<\/code><\/pre>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h3 class=\"wp-block-heading\"><a href=\"https:\/\/kamacoder.com\/problempage.php?pid=1178\">106. \u5c9b\u5c7f\u7684\u5468\u957f<\/a>\u2705<\/h3>\n\n\n\n<p><strong><em>\u4e0d\u7528\u6df1\u641c\u5e7f\u641c \u76f4\u63a5\u904d\u5386\u6bcf\u4e00\u5757\u9646\u5730 \u68c0\u67e5\u5468\u56f4\u56db\u5757 \u5982\u679c\u662f\u6c34\u5468\u957f\u5c31+1 <\/em><\/strong><\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>#include&lt;bits\/stdc++.h&gt;\nusing namespace std;\n \nint n, m, res;\nint dir&#91;4]&#91;2] = {0, 1, 0, -1, 1, 0, -1, 0}; \n\nint main() {\n    cin &gt;&gt; n &gt;&gt; m;\n    vector&lt;vector&lt;int&gt;&gt; grid(n, vector&lt;int&gt;(m));\n    int x, y;\n    for(int i = 0; i &lt; n; i++) {\n        for(int j = 0; j &lt; m; j++) {\n            cin &gt;&gt; grid&#91;i]&#91;j];\n        }\n    }\n    \n    int nearx, neary;\n    for(int i = 0; i &lt; n; i++) {\n        for(int j = 0; j &lt; m; j++) {\n            if(grid&#91;i]&#91;j]) { \/\/\u904d\u5386\u9646\u5730\u5468\u56f4\u7684\u6c34\u7684\u6570\u91cf\u5c31\u662f\u5468\u957f\n                for(int k = 0; k &lt; 4; k++) {\n                    nearx = i + dir&#91;k]&#91;0];\n                    neary = j + dir&#91;k]&#91;1];\n                    if(nearx &lt; 0 || nearx &gt;= n || neary &lt; 0 || neary &gt;= m) {\n                        res++;\n                        continue;\n                    }\n                    if(grid&#91;nearx]&#91;neary] == 0) {\n                        res++;\n                    }\n                    \n                }\n            }\n        }\n    }\n    \n    cout &lt;&lt; res &lt;&lt; endl;\n\n    return 0;\n}<\/code><\/pre>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h2 class=\"wp-block-heading\">\u5e76\u67e5\u96c6<\/h2>\n\n\n\n<h3 class=\"wp-block-heading\"><a href=\"https:\/\/kamacoder.com\/problempage.php?pid=1179\">107. \u5bfb\u627e\u5b58\u5728\u7684\u8def\u5f84<\/a>\u2705<\/h3>\n\n\n\n<p><strong><em>\u5e76\u67e5\u96c6\u6a21\u677f\u9898<\/em><\/strong><\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>#include&lt;bits\/stdc++.h&gt;\nusing namespace std;\n \nint n, m, bg, ed;\nvector&lt;int&gt; fa;\n\nvoid init() {\n    for(int i = 1; i &lt;= n; i++) fa&#91;i] = i;\n}\n\nint find(int x) {\n    if(fa&#91;x] == x) return x;\n    return fa&#91;x] = find(fa&#91;x]);\n}\n\nvoid merge(int u, int v) {\n    int fu = find(u);\n    int fv = find(v);\n    if(fu == fv) return ;\n    fa&#91;fv] = fu;\n}\n\nbool isSame(int u, int v) {\n    int fu = find(u);\n    int fv = find(v);\n    return fu == fv;\n}\n\nint main() {\n    cin &gt;&gt; n &gt;&gt; m;\n    fa.resize(n+1);\n    \n    int x, y;\n    vector&lt;pair&lt;int, int&gt;&gt; edges;\n    for(int i = 0; i &lt; m; i++) {\n        cin &gt;&gt; x &gt;&gt; y;\n        edges.push_back(make_pair(x, y));\n      \n    }\n    cin &gt;&gt;bg &gt;&gt; ed;\n    \n    init();\n    \n    for(int i = 0; i &lt; m; i++) {\n        merge(edges&#91;i].first, edges&#91;i].second);\n    }\n    \n    if(isSame(bg, ed)) cout &lt;&lt; 1 &lt;&lt; endl;\n    else cout &lt;&lt; 0 &lt;&lt; endl;\n\n    return 0;\n}<\/code><\/pre>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h3 class=\"wp-block-heading\"><a href=\"https:\/\/kamacoder.com\/problempage.php?pid=1181\">108. \u5197\u4f59\u8fde\u63a5<\/a>\u2705<\/h3>\n\n\n\n<p><em><strong>\u6211\u7684\u601d\u8def\uff1a\u904d\u5386\u6bcf\u6761\u8fb9\uff0c\u770b\u53bb\u6389\u5b83\u7528\u5e76\u67e5\u96c6\u68c0\u67e5\u662f\u5426\u4f9d\u7136\u8fde\u901a\uff08\u7e41\u7410\uff0c\u76f8\u5f53\u4e8e\u7528\u4e86n-1\u5957\u5e76\u67e5\u96c6\uff09<\/strong><\/em><\/p>\n\n\n\n<p><strong><em>\u6807\u51c6\u601d\u8def\uff1a\u53ea\u9700\u904d\u5386\u6bcf\u4e00\u6761\u8fb9\uff0c\u5224\u65ad\u8282\u70b9A\u548c\u8282\u70b9B\u662f\u5426\u5728\u540c\u4e00\u4e2a\u96c6\u5408\uff0c\u5982\u679c\u4e0d\u5728\uff0c\u5c31merge\uff1b\u5982\u679c\u5728\uff0c\u8bf4\u660e\u518d\u5c06\u8fd9\u6761\u8fb9\u52a0\u4e0a\u5c31\u4e00\u5b9a\u4f1a\u51fa\u73b0\u73af\uff08\u53ea\u7528\u4e86\u4e00\u5957\u5e76\u67e5\u96c6\uff09<\/em><\/strong><\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>\/\/<em><strong>\u6211\u7684\u601d\u8def<\/strong><\/em>\n#include&lt;bits\/stdc++.h&gt;\nusing namespace std;\n \nint n;\nvector&lt;int&gt; fa;\n\nvoid init() {\n    for(int i = 0; i &lt; n; i++) fa&#91;i] = i;\n}\n\nint find(int x) {\n    if(fa&#91;x] == x) return x;\n    return fa&#91;x] = find(fa&#91;x]);\n}\n\nvoid merge(int u, int v) {\n    int fu = find(u);\n    int fv = find(v);\n    if(fu == fv) return ;\n    fa&#91;fv] = fu;\n}\n\nbool isSame(int u, int v) {\n    int fu = find(u);\n    int fv = find(v);\n    return fu == fv;\n}\n\nint main() {\n    cin &gt;&gt; n;\n    fa.resize(n+1);\n    \n    int x, y;\n    vector&lt;pair&lt;int, int&gt;&gt; edges;\n    for(int i = 0; i &lt; n; i++) {\n        cin &gt;&gt; x &gt;&gt; y;\n        edges.push_back(make_pair(x, y));\n      \n    }\n    \n    \/\/\u904d\u5386\u6bcf\u6761\u8fb9\uff0c\u770b\u53bb\u6389\u5b83\u662f\u5426\u4f9d\u7136\u8fde\u901a\n    for(int i = n-1; i &gt;= 0; i--) { \/\/\u4e3a\u4e86\u8f93\u51fa\u8981\u6c42\uff0c\u4ece\u540e\u5f80\u524d\u904d\u5386\n        init();\n        \/\/ cout &lt;&lt; \"\u53bb\u6389\u8fb9\" &lt;&lt; edges&#91;i].first &lt;&lt; edges&#91;i].second &lt;&lt; endl;\n        for(int j = 0; j &lt; n; j++) {\n            if(i == j) continue;\n            merge(edges&#91;j].first, edges&#91;j].second);\n        }\n        \/\/ for(int k = 1; k &lt;= n; k++) cout &lt;&lt; \"fa&#91;\" &lt;&lt; k &lt;&lt; \"] = \" &lt;&lt; fa&#91;k] &lt;&lt; endl;\n        bool flag = true;\n        for(int k = 1; k &lt; n; k++) { \/\/\u68c0\u6d4b\u662f\u5426\u8fde\u901a\n            if(!isSame(0, k)) {\n                \/\/ cout &lt;&lt; \"false\" &lt;&lt; endl;\n                flag = false;\n                break;\n            }\n        }\n        if(flag) {\n            cout &lt;&lt; edges&#91;i].first &lt;&lt; \" \" &lt;&lt; edges&#91;i].second &lt;&lt; endl;\n            return 0;\n        }\n    }\n \n}<\/code><\/pre>\n\n\n\n<pre class=\"wp-block-code\"><code>\/\/\u6807\u51c6\u601d\u8def\n#include&lt;bits\/stdc++.h&gt;\nusing namespace std;\n \nint n;\nvector&lt;int&gt; fa;\n\nvoid init() {\n    for(int i = 0; i &lt; n; i++) fa&#91;i] = i;\n}\n\nint find(int x) {\n    if(fa&#91;x] == x) return x;\n    return fa&#91;x] = find(fa&#91;x]);\n}\n\nvoid merge(int u, int v) {\n    int fu = find(u);\n    int fv = find(v);\n    if(fu == fv) return ;\n    fa&#91;fv] = fu;\n}\n\nbool isSame(int u, int v) {\n    int fu = find(u);\n    int fv = find(v);\n    return fu == fv;\n}\n\nint main() {\n    cin &gt;&gt; n;\n    fa.resize(n+1);\n    init();\n    \n    int x, y;\n    for(int i = 0; i &lt; n; i++) {\n        cin &gt;&gt; x &gt;&gt; y;\n        if(isSame(x, y)) {\n            cout &lt;&lt; x &lt;&lt; \" \" &lt;&lt; y &lt;&lt; endl;\n            return 0;\n        }\n        merge(x, y);\n    }\n \n}<\/code><\/pre>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h3 class=\"wp-block-heading\"><a href=\"https:\/\/kamacoder.com\/problempage.php?pid=1182\">109. \u5197\u4f59\u8fde\u63a5II<\/a>\u274c<\/h3>\n\n\n\n<p><em><strong>\u4e0e\u4e0a\u9898\u7c7b\u4f3c\uff0c\u4f46\u8981\u66f4\u590d\u6742\u4e00\u4e9b\uff0c\u8be6\u89c1<a href=\"https:\/\/programmercarl.com\/kamacoder\/0109.%E5%86%97%E4%BD%99%E8%BF%9E%E6%8E%A5II.html#%E6%80%9D%E8%B7%AF\">\u4ee3\u7801\u968f\u60f3\u5f55\u9898\u89e3<\/a><\/strong><\/em><\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>#include&lt;bits\/stdc++.h&gt;\nusing namespace std;\n \nint n;\nvector&lt;vector&lt;int&gt;&gt; edges;\nvector&lt;int&gt; inDegree; \/\/\u7edf\u8ba1\u5165\u5ea6\nvector&lt;int&gt; twoDegree; \/\/\u8bb0\u5f55\u5165\u5ea6\u4e3a2\u7684\u8fb9\uff08\u5982\u679c\u6709\u7684\u8bdd\u5c31\u4e24\u6761\u8fb9\uff09\nvector&lt;int&gt; fa;\n \nvoid init() {\n    for(int i = 1; i &lt;= n; i++) fa&#91;i] = i;\n}\n \nint find(int x) {\n    if(fa&#91;x] == x) return x;\n    return fa&#91;x] = find(fa&#91;x]);\n}\n \nvoid merge(int u, int v) {\n    int fu = find(u);\n    int fv = find(v);\n    if(fu == fv) return ;\n    fa&#91;fv] = fu;\n}\n \nbool isSame(int u, int v) {\n    int fu = find(u);\n    int fv = find(v);\n    return fu == fv;\n}\n\n\/\/\u5220\u4e00\u6761\u8fb9\u4e4b\u540e\u5224\u65ad\u662f\u4e0d\u662f\u6811\nbool isTree(int deleteEdge) {\n    init(); \/\/ \u521d\u59cb\u5316\u5e76\u67e5\u96c6\n    for(int i = 0; i &lt; n; i++) {\n        if(i == deleteEdge) continue; \/\/\u76f8\u5f53\u4e8e\u5220\u9664\u4e86\u8be5\u8fb9\n        if(isSame(edges&#91;i]&#91;0], edges&#91;i]&#91;1])) { \/\/\u6784\u6210\u6709\u5411\u73af\u4e86\uff0c\u4e00\u5b9a\u4e0d\u662f\u6811\n            return false;\n        }\n        merge(edges&#91;i]&#91;0], edges&#91;i]&#91;1]);\n    }\n    return true;\n}\n\n\/\/\u5728\u6709\u5411\u56fe\u91cc\u627e\u5230\u5220\u9664\u7684\u90a3\u6761\u8fb9\uff0c\u4f7f\u5176\u53d8\u6210\u6811\nvoid findRemoveEdge() {\n    init(); \/\/ \u521d\u59cb\u5316\u5e76\u67e5\u96c6\n    for(int i = 0; i &lt; n; i++) { \/\/\u904d\u5386\u6240\u6709\u7684\u8fb9\n        if(isSame(edges&#91;i]&#91;0], edges&#91;i]&#91;1])) { \/\/\u6784\u6210\u6709\u5411\u73af\u4e86\uff0c\u5c31\u662f\u8981\u5220\u9664\u7684\u8fb9\n            cout &lt;&lt; edges&#91;i]&#91;0] &lt;&lt; \" \" &lt;&lt; edges&#91;i]&#91;1];\n            return;\n        } else{\n            merge(edges&#91;i]&#91;0], edges&#91;i]&#91;1]);\n        }\n    }\n}\n\nint main() {\n    cin &gt;&gt; n;\n    fa.resize(n+1);\n    inDegree.resize(n+1, 0); \n    init();\n    \n    int x, y;\n    for(int i = 0; i &lt; n; i++) {\n        cin &gt;&gt; x &gt;&gt; y;\n        inDegree&#91;y]++;\n        edges.push_back({x, y});\n    }\n    \n    \/\/\u904d\u5386\u627e\u51fa\u5165\u5ea6\u4e3a2\u7684\u8fb9 \n    for(int i = n-1; i &gt;= 0; i--) { \/\/\u5012\u5e8f\u904d\u5386\u662f\u4e3a\u4e86\u9898\u76ee\u8981\u6c42\uff0c\u8f93\u51fa\u6700\u540e\u51fa\u73b0\u7684\u4e00\u6761\u8fb9\n        if(inDegree&#91;edges&#91;i]&#91;1]] == 2) {\n            twoDegree.push_back(i);\n        }\n    }\n    \n    if(twoDegree.size() &gt; 0) {\n        if(isTree(twoDegree&#91;0])) {\n            cout &lt;&lt; edges&#91;twoDegree&#91;0]]&#91;0] &lt;&lt; \" \" &lt;&lt; edges&#91;twoDegree&#91;0]]&#91;1];\n        } else{\n            cout &lt;&lt; edges&#91;twoDegree&#91;1]]&#91;0] &lt;&lt; \" \" &lt;&lt; edges&#91;twoDegree&#91;1]]&#91;1];\n        }\n        return 0;\n    }\n    \n    \/\/\u660e\u786e\u6ca1\u6709\u5165\u5ea6\u4e3a2\u7684\u60c5\u51b5\uff0c\u90a3\u4e48\u4e00\u5b9a\u6709\u6709\u5411\u73af\uff0c\u627e\u5230\u6784\u6210\u73af\u7684\u8fb9\u8fd4\u56de\u5c31\u53ef\u4ee5\u4e86\n    findRemoveEdge();\n \n}<\/code><\/pre>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h2 class=\"wp-block-heading\">\u6700\u5c0f\u751f\u6210\u6811<\/h2>\n\n\n\n<h3 class=\"wp-block-heading\"><a href=\"https:\/\/kamacoder.com\/problempage.php?pid=1053\">53. \u5bfb\u5b9d\uff08\u7b2c\u4e03\u671f\u6a21\u62df\u7b14\u8bd5\uff09<\/a>\u2705<\/h3>\n\n\n\n<p><strong><em>\u6700\u5c0f\u751f\u6210\u6811\u6a21\u677f\u9898<\/em><\/strong><\/p>\n\n\n\n<p><strong>Kruskal<em><strong><em><strong>\u7b97\u6cd5<\/strong><\/em><\/strong><\/em>\u662f\u7ef4\u62a4\u8fb9\u7684\u96c6\u5408\uff0c<strong>\u800c<\/strong>prim\u7b97\u6cd5\u662f\u7ef4\u62a4\u8282\u70b9\u7684\u96c6\u5408<\/strong> <\/p>\n\n\n\n<p><strong><em>Kruskal\u65f6\u95f4\u590d\u6742\u5ea6\u4e3anlogn\uff0cn\u4e3a\u8fb9\u7684\u6570\u91cf\uff1bprim\u65f6\u95f4\u590d\u6742\u5ea6\u4e3aO(n^2)\uff0cn\u4e3a\u70b9\u7684\u6570\u91cf<\/em><\/strong><\/p>\n\n\n\n<p><em><strong>\u56e0\u6b64\uff0c&nbsp;\u7a00\u758f\u56fe\u7528Kruskal\u7b97\u6cd5\u66f4\u4f18\uff0c\u7a20\u5bc6\u56fe\u7528prim\u7b97\u6cd5\u66f4\u4f18\uff08\u5982\u679c\u9898\u76ee\u8981\u6c42\u8f93\u51fa\u9009\u4e2d\u7684\u8fb9\uff0c\u7528Kruskal\u4f1a\u65b9\u4fbf\u5f88\u591a\uff09<\/strong><\/em><\/p>\n\n\n\n<p><em>Kruskal\uff1a<\/em><\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>#include&lt;bits\/stdc++.h&gt;\nusing namespace std;\n\nint n, m;\nint fa&#91;10005];\n\nstruct edge {\n    int u, v, c;\n};\n\nbool cmp(edge x, edge y) {\n    return x.c &lt; y.c;\n}\n\nvoid init() {\n    for(int i = 1; i &lt;= n; i++) fa&#91;i] = i;    \n}\n\nint find(int x) {\n    if(fa&#91;x] == x) return x;\n    return fa&#91;x] = find(fa&#91;x]);\n}\n\nvoid merge(int u, int v) {\n    int fu = find(u);\n    int fv = find(v);\n    if(fu == fv) return ;\n    fa&#91;fv] = fu;\n}\n\nbool isSame(int u, int v) {\n    int fu = find(u);\n    int fv = find(v);\n    return fu == fv;\n}\n\nint main() {\n    cin &gt;&gt; n &gt;&gt; m;\n    vector&lt;edge&gt; edges;\n    \n    struct edge ed;\n    for(int i = 0; i &lt; m; i++) {\n        cin &gt;&gt; ed.u &gt;&gt; ed.v &gt;&gt; ed.c;\n        edges.push_back(ed); \n    }\n    \n    sort(edges.begin(), edges.end(), cmp);\n    \n    \/\/ for(const auto &amp;ed : edges) cout &lt;&lt; ed.u &lt;&lt; \" \" &lt;&lt; ed.v &lt;&lt; \" \" &lt;&lt;  ed.c &lt;&lt; endl;\n    \n    init();\n    \n    int cnt = 0;\n    int res = 0;\n    for(const auto &amp;ed : edges) {\n        if(isSame(ed.u, ed.v)) continue;\n        merge(ed.u, ed.v);\n        res += ed.c;\n        cnt++;\n        if(cnt == n-1) break;\n    }\n    \n    cout &lt;&lt; res &lt;&lt; endl;\n    \n    return 0;\n}<\/code><\/pre>\n\n\n\n<p><em>prim\uff1a<\/em><\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>#include&lt;bits\/stdc++.h&gt;\nusing namespace std;\n\nint main() {\n    int n, m;\n    int x, y, k;\n    cin &gt;&gt; n &gt;&gt; m;\n \n    vector&lt;vector&lt;int&gt;&gt; grid(n + 1, vector&lt;int&gt;(n + 1, 10001)); \/\/\u9ed8\u8ba4\u6700\u5927\u503c\n    while(m--) {\n        cin &gt;&gt; x &gt;&gt; y &gt;&gt; k;\n        \/\/\u56e0\u4e3a\u662f\u53cc\u5411\u56fe\uff0c\u6240\u4ee5\u4e24\u4e2a\u65b9\u5411\u90fd\u8981\u586b\u4e0a\n        grid&#91;x]&#91;y] = k;\n        grid&#91;y]&#91;x] = k;\n\n    }\n    \n    vector&lt;int&gt; minDist(n + 1, 10001); \/\/\u6240\u6709\u8282\u70b9\u5230\u6700\u5c0f\u751f\u6210\u6811\u7684\u6700\u5c0f\u8ddd\u79bb\n    vector&lt;bool&gt; isInTree(n + 1, false); \/\/\u8fd9\u4e2a\u8282\u70b9\u662f\u5426\u5728\u6811\u91cc\n\n    \/\/\u5faa\u73afn-1\u6b21\uff0c\u5efa\u7acbn-1\u6761\u8fb9\n    for (int i = 1; i &lt; n; i++) {\n        \/\/\u7b2c\u4e00\u6b65\uff1a\u9009\u8ddd\u79bb\u751f\u6210\u6811\u6700\u8fd1\u7684\u8282\u70b9\n        int cur = -1; \/\/\u9009\u4e2d\u54ea\u4e2a\u8282\u70b9\uff0c\u52a0\u5165\u6700\u5c0f\u751f\u6210\u6811\n        int minVal = INT_MAX;\n        for(int j = 1; j &lt;= n; j++) { \/\/\u8fd9\u91cc\u4e0b\u6807\u4ece1\u5f00\u59cb\n            if(!isInTree&#91;j] &amp;&amp; minDist&#91;j] &lt; minVal) {\n                minVal = minDist&#91;j];\n                cur = j;\n            }\n        }\n        \/\/\u7b2c\u4e8c\u6b65\uff1a\u6700\u8fd1\u8282\u70b9\uff08cur\uff09\u52a0\u5165\u751f\u6210\u6811\n        isInTree&#91;cur] = true;\n\n        \/\/\u7b2c\u4e09\u6b65\uff1a\u66f4\u65b0\u975e\u751f\u6210\u6811\u8282\u70b9\u5230\u751f\u6210\u6811\u7684\u8ddd\u79bb\uff08\u5373\u66f4\u65b0minDist\u6570\u7ec4\uff09\n        for(int j = 1; j &lt;= n; j++) {\n            if(!isInTree&#91;j] &amp;&amp; grid&#91;cur]&#91;j] &lt; minDist&#91;j]) {\n                minDist&#91;j] = grid&#91;cur]&#91;j];\n            }\n        }\n    }\n    \n    int res = 0;\n    for(int i = 2; i &lt;= n; i++) { \/\/\u4e0d\u8ba1\u7b2c\u4e00\u4e2a\u9876\u70b9\uff0c\u56e0\u4e3a\u7edf\u8ba1\u7684\u662f\u8fb9\u7684\u6743\u503c\uff0cn\u4e2a\u8282\u70b9\u6709n-1\u6761\u8fb9\n        res += minDist&#91;i];\n    }\n    cout &lt;&lt; res &lt;&lt; endl;\n    \n    return 0;\n}\n<\/code><\/pre>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h2 class=\"wp-block-heading\">\u62d3\u6251\u6392\u5e8f<\/h2>\n\n\n\n<h3 class=\"wp-block-heading\"><a href=\"https:\/\/kamacoder.com\/problempage.php?pid=1191\">117. \u8f6f\u4ef6\u6784\u5efa<\/a>\u274c<\/h3>\n\n\n\n<p><em><strong>\u62d3\u6251\u6392\u5e8f\u6a21\u677f\u9898<\/strong><\/em><\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>#include&lt;bits\/stdc++.h&gt;\nusing namespace std;\n\nint main() {\n    int n, m;\n    cin &gt;&gt; n &gt;&gt; m;\n    \n    vector&lt;int&gt; inDegree(n, 0);\n    unordered_map&lt;int, vector&lt;int&gt;&gt; umap;\/\/ \u8bb0\u5f55\u6587\u4ef6\u4f9d\u8d56\u5173\u7cfb\n    vector&lt;int&gt; res; \n    \n    int u, v;\n    for(int i = 0; i &lt; m; i++) {\n        cin &gt;&gt; u &gt;&gt; v;\n        inDegree&#91;v]++;\n        umap&#91;u].push_back(v);\n    }\n    \n    queue&lt;int&gt; que;\n    for(int i = 0; i &lt; n; i++) {\n        if(inDegree&#91;i] == 0) {\n            que.push(i);\n        }\n    }\n    \n    while(!que.empty()) {\n        int cur = que.front();\n        que.pop();\n        res.push_back(cur);\n        \n        vector&lt;int&gt; files = umap&#91;cur]; \/\/\u83b7\u53d6\u8be5\u6587\u4ef6\u6307\u5411\u7684\u6587\u4ef6\n        \/\/\u5982\u679c\u8be5\u6587\u4ef6\u6709\u540e\u7eed\u6587\u4ef6\uff0c\u8981\u628a\u5b83\u4eec\u7684\u5165\u5ea6\u51cf\u4e00\uff0c\u76f8\u5f53\u4e8e\u5728\u56fe\u4e2d\u5220\u9664cur\u8282\u70b9\n        if(!files.empty()) { \n            for(const auto &amp;file : files) {\n                inDegree&#91;file]--;\n                if(!inDegree&#91;file]) que.push(file);\n            }\n        }\n    }\n    \n    if(res.size() == n) {\n        cout &lt;&lt; res&#91;0];\n        for(int i = 1; i &lt; n; i++) cout &lt;&lt; \" \"&lt;&lt; res&#91;i];\n    } else {\n        cout &lt;&lt; -1 &lt;&lt; endl;\n    }\n    \n    return 0;\n}<\/code><\/pre>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h2 class=\"wp-block-heading\">\u6700\u77ed\u8def\u7b97\u6cd5<\/h2>\n\n\n\n<h3 class=\"wp-block-heading\"><a href=\"https:\/\/kamacoder.com\/problempage.php?pid=1047\">47. \u53c2\u52a0\u79d1\u5b66\u5927\u4f1a\uff08\u7b2c\u516d\u671f\u6a21\u62df\u7b14\u8bd5\uff09<\/a><\/h3>\n\n\n\n<p><em><strong>\u6700\u77ed\u8def\u5f84dijkstra\u7b97\u6cd5\u6a21\u677f\u9898<\/strong><\/em><\/p>\n\n\n\n<p><em><strong>\u6734\u7d20\u7248\uff1a\u91c7\u7528\u90bb\u63a5\u77e9\u9635\u5b58\u50a8\u56fe\uff0c\u9002\u7528\u4e8e\u7a20\u5bc6\u56fe<\/strong><\/em><\/p>\n\n\n\n<p><em><strong>\u5806\u4f18\u5316\u7248\uff1a\u91c7\u7528\u90bb\u63a5\u8868\u5b58\u50a8\u56fe\uff0c\u9002\u7528\u4e8e\u7a00\u758f\u56fe<\/strong><\/em><\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>\/\/<em><strong>dijkstra\u7b97\u6cd5\u6734\u7d20\u7248<\/strong><\/em>\n#include&lt;bits\/stdc++.h&gt;\nusing namespace std;\nint main() {\n    int n, m, s, e, w;\n    cin &gt;&gt; n &gt;&gt; m;\n    vector&lt;vector&lt;int&gt;&gt; grid(n+1, vector&lt;int&gt;(n+1, INT_MAX));\n    for(int i = 0; i &lt; m; i++) {\n        cin &gt;&gt; s &gt;&gt; e &gt;&gt; w;\n        grid&#91;s]&#91;e] = w;\n    }\n    \n    vector&lt;int&gt; minDist(n+1, INT_MAX);\n    vector&lt;bool&gt; visited(n+1, false);\n    \n    minDist&#91;1] = 0;\n    \n    for(int i = 1; i &lt;= n; i++) {\n        int cur = 1;\n        int minVal = INT_MAX;\n        \n        for(int v = 1; v &lt;= n; v++) {\n            if(!visited&#91;v] &amp;&amp; minDist&#91;v] &lt; minVal) {\n                cur = v;\n                minVal = minDist&#91;v];\n            }\n        }\n        \n        visited&#91;cur] = true;\n        \n        for(int v = 1; v &lt;= n; v++) {\n            if(!visited&#91;v] &amp;&amp; grid&#91;cur]&#91;v] != INT_MAX &amp;&amp; minDist&#91;cur] + grid&#91;cur]&#91;v] &lt; minDist&#91;v]) {\n                minDist&#91;v] = minDist&#91;cur] + grid&#91;cur]&#91;v];\n            }\n        }\n        \n        \/\/ \u6253\u5370\u65e5\u5fd7\uff1a\n        \/\/ cout &lt;&lt; \"select:\" &lt;&lt; cur &lt;&lt; endl;\n        \/\/ for (int v = 1; v &lt;= n; v++) cout &lt;&lt;  v &lt;&lt; \":\" &lt;&lt; minDist&#91;v] &lt;&lt; \" \";\n        \/\/ cout &lt;&lt; endl &lt;&lt; endl;\n    }\n    \n    if(minDist&#91;n] == INT_MAX) cout &lt;&lt; -1 &lt;&lt; endl;\n    else cout &lt;&lt; minDist&#91;n] &lt;&lt; endl;\n    \n    return 0;\n}<\/code><\/pre>\n\n\n\n<pre class=\"wp-block-code\"><code>\/\/<em><strong>dijkstra\u7b97\u6cd5\u5806\u4f18\u5316\u7248<\/strong><\/em>\n#include&lt;bits\/stdc++.h&gt;\nusing namespace std;\n\/\/\u5c0f\u9876\u5806\nclass myComparison {\npublic:\n    \/\/\u8c13\u8bcd\n    bool operator()(const pair&lt;int, int&gt;&amp; lhs, const pair&lt;int, int&gt;&amp; rhs) {\n        return lhs.second &gt; rhs.second;\n    }\n};\n\/\/\u5b9a\u4e49\u4e00\u4e2a\u7ed3\u6784\u4f53\u6765\u8868\u793a\u5e26\u6743\u91cd\u7684\u8fb9\nstruct Edge {\n    int to;  \/\/\u90bb\u63a5\u9876\u70b9\n    int val; \/\/\u8fb9\u7684\u6743\u91cd\n\n    Edge(int t, int w): to(t), val(w) {}  \/\/\u6784\u9020\u51fd\u6570\n};\n\nint main() {\n    int n, m, p1, p2, val;\n    cin &gt;&gt; n &gt;&gt; m;\n\n    vector&lt;list&lt;Edge&gt;&gt; grid(n + 1);\n\n    for(int i = 0; i &lt; m; i++){\n        cin &gt;&gt; p1 &gt;&gt; p2 &gt;&gt; val; \n        grid&#91;p1].push_back(Edge(p2, val));\n\n    }\n\n    vector&lt;int&gt; minDist(n + 1, INT_MAX);\n    vector&lt;bool&gt; visited(n + 1, false); \n    \n    \/\/\u4f18\u5148\u961f\u5217\u4e2d\u5b58\u653epair&lt;\u8282\u70b9\uff0c\u6e90\u70b9\u5230\u8be5\u8282\u70b9\u7684\u6743\u503c&gt;\n    priority_queue&lt;pair&lt;int, int&gt;, vector&lt;pair&lt;int, int&gt;&gt;, myComparison&gt; pq;\n\n    pq.push(pair&lt;int, int&gt;(1, 0)); \n    minDist&#91;1] = 0;  \n\n    while(!pq.empty()) {\n        pair&lt;int, int&gt; cur = pq.top(); \n        pq.pop();\n\n        if(visited&#91;cur.first]) continue;\n\n        visited&#91;cur.first] = true;\n\n        for(Edge edge : grid&#91;cur.first]) {\n            if(!visited&#91;edge.to] &amp;&amp; minDist&#91;cur.first] + edge.val &lt; minDist&#91;edge.to]) { \n                minDist&#91;edge.to] = minDist&#91;cur.first] + edge.val;\n                pq.push(pair&lt;int, int&gt;(edge.to, minDist&#91;edge.to]));\n            }\n        }\n    }\n\n    if(minDist&#91;n] == INT_MAX) cout &lt;&lt; -1 &lt;&lt; endl; \n    else cout &lt;&lt; minDist&#91;n] &lt;&lt; endl; \n    \n    return 0;\n}\n<\/code><\/pre>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h3 class=\"wp-block-heading\"><a href=\"https:\/\/kamacoder.com\/problempage.php?pid=1152\">94. \u57ce\u5e02\u95f4\u8d27\u7269\u8fd0\u8f93 I<\/a><\/h3>\n\n\n\n<p><strong><em>\u6700\u77ed\u8def\u5f84Bellman_ford\u7b97\u6cd5\u6a21\u677f\u9898<\/em>\uff08\u9002\u7528\u4e8e\u8fb9\u6743\u503c\u542b\u8d1f\u6570\u7684\u60c5\u51b5\uff09<\/strong><\/p>\n\n\n\n<p><strong><em>\u4f18\u5316\u7248\uff1a<\/em><\/strong><em><strong><a href=\"https:\/\/programmercarl.com\/kamacoder\/0094.%E5%9F%8E%E5%B8%82%E9%97%B4%E8%B4%A7%E7%89%A9%E8%BF%90%E8%BE%93I-SPFA.html\">Bellman_ford\u961f\u5217\u4f18\u5316\uff08\u5373<em><strong>SPFA<\/strong><\/em>\u7b97\u6cd5\uff09<\/a><\/strong><\/em><\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>#include&lt;bits\/stdc++.h&gt;\nusing namespace std;\nint main() {\n    int n, m;\n    cin &gt;&gt; n &gt;&gt; m;\n    vector&lt;vector&lt;int&gt;&gt; edges;\n    int x, y, v;\n    for(int i = 0; i &lt; m; i++) {\n        cin &gt;&gt; x &gt;&gt; y &gt;&gt; v;\n        edges.push_back({x, y, v});\n    }\n    \n    int begin = 1;\n    int end = n;\n    vector&lt;int&gt; minDist(n+1, INT_MAX);\n    minDist&#91;begin] = 0;\n    \n    \/\/\u677e\u5f1bn-1\u6b21\n    for(int k = 1; k &lt;= n-1; k++) {\n        for(const vector&lt;int&gt; &amp;edge : edges) { \/\/\u904d\u5386\u6bcf\u4e00\u6761\u8fb9\n            int from = edge&#91;0];\n            int to = edge&#91;1];\n            int value = edge&#91;2];\n            \/\/\u6838\u5fc3\n            if(minDist&#91;from] != INT_MAX &amp;&amp; minDist&#91;to] &gt; minDist&#91;from] + value) {\n                minDist&#91;to] = minDist&#91;from] + value;\n            }\n        }\n    }\n    \n    if(minDist&#91;end] == INT_MAX) cout &lt;&lt; \"unconnected\" &lt;&lt; endl;\n    else cout &lt;&lt; minDist&#91;end] &lt;&lt; endl;\n    \n    return 0;\n}<\/code><\/pre>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h3 class=\"wp-block-heading\"><a href=\"https:\/\/kamacoder.com\/problempage.php?pid=1153\">95. \u57ce\u5e02\u95f4\u8d27\u7269\u8fd0\u8f93 II<\/a><\/h3>\n\n\n\n<p><strong><em>\u4f9d\u7136\u662f\u6700\u77ed\u8def\u5f84Bellman_ford\u7b97\u6cd5\u6a21\u677f\u9898\uff0c\u5728<a href=\"https:\/\/kamacoder.com\/problempage.php?pid=1152\">\u4e0a\u9898<\/a>\u7684\u57fa\u7840\u4e0a\u589e\u52a0\u4e86\u542b\u6709\u8d1f\u6743\u56de\u8def\u7684\u60c5\u51b5<\/em><\/strong><\/p>\n\n\n\n<p><em><strong>\u6838\u5fc3\u601d\u8def\u5c31\u662f\u5728\u4e0a\u9898\u7684\u57fa\u7840\u4e0a\uff0c\u518d\u591a\u677e\u5f1b\u4e00\u6b21\uff0c\u770bminDist\u6570\u7ec4\u662f\u5426\u53d1\u751f\u53d8\u5316<\/strong><\/em><\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>#include&lt;bits\/stdc++.h&gt;\nusing namespace std;\nint main() {\n    int n, m;\n    cin &gt;&gt; n &gt;&gt; m;\n    vector&lt;vector&lt;int&gt;&gt; edges;\n    int x, y, v;\n    for(int i = 0; i &lt; m; i++) {\n        cin &gt;&gt; x &gt;&gt; y &gt;&gt; v;\n        edges.push_back({x, y, v});\n    }\n    \n    int begin = 1;\n    int end = n;\n    vector&lt;int&gt; minDist(n+1, INT_MAX);\n    minDist&#91;begin] = 0;\n    bool circle = false;\n    \n    \/\/\u677e\u5f1bn-1\u6b21\n    for(int k = 1; k &lt;= n; k++) {\n        for(const vector&lt;int&gt; &amp;edge : edges) { \/\/\u904d\u5386\u6bcf\u4e00\u6761\u8fb9\n            int from = edge&#91;0];\n            int to = edge&#91;1];\n            int value = edge&#91;2];\n            \/\/\u6838\u5fc3\n            if(k == n) {\n                if(minDist&#91;from] != INT_MAX &amp;&amp; minDist&#91;to] &gt; minDist&#91;from] + value) circle = true;\n            } else {\n                if(minDist&#91;from] != INT_MAX &amp;&amp; minDist&#91;to] &gt; minDist&#91;from] + value) {\n                    minDist&#91;to] = minDist&#91;from] + value;\n                }\n            }\n        }\n    }\n    \n    if(circle) cout &lt;&lt; \"circle\" &lt;&lt; endl;\n    else if(minDist&#91;end] == INT_MAX) cout &lt;&lt; \"unconnected\" &lt;&lt; endl;\n    else cout &lt;&lt; minDist&#91;end] &lt;&lt; endl;\n    \n    return 0;\n}<\/code><\/pre>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h3 class=\"wp-block-heading\"><a href=\"https:\/\/kamacoder.com\/problempage.php?pid=1154\">96. \u57ce\u5e02\u95f4\u8d27\u7269\u8fd0\u8f93 III<\/a><\/h3>\n\n\n\n<p><strong><em>\u4f9d\u7136\u662f\u6700\u77ed\u8def\u5f84Bellman_ford\u7b97\u6cd5\u6a21\u677f\u9898\uff0c\u5728<a href=\"https:\/\/kamacoder.com\/problempage.php?pid=1152\"><\/a><a href=\"https:\/\/kamacoder.com\/problempage.php?pid=1152\"><\/a><a href=\"https:\/\/kamacoder.com\/problempage.php?pid=1153\">95. \u57ce\u5e02\u95f4\u8d27\u7269\u8fd0\u8f93 II<\/a>\u7684\u57fa\u7840\u4e0a\u589e\u52a0\u4e86\u6700\u77ed\u8def\u5f84\u9014\u5f84\u8282\u70b9\u6570\u91cf\u7684\u9650\u5236<\/em><\/strong><\/p>\n\n\n\n<p><em><strong>\u65e2\u7136\u4e4b\u524d\u662f\u677e\u5f1bn-1\u6b21\uff0c\u90a3\u4e48\u73b0\u5728\u6539\u4e3a\u677e\u5f1bk+1\u6b21\u5373\u53ef<\/strong><\/em><strong><em>\uff08\u56e0\u4e3a\u9014\u5f84\u8282\u70b9\u4e0d\u5305\u62ec1\u548cn\uff0c\u56e0\u6b64\u5b9e\u9645\u4e0a\u662fk+2\u4e2a\u8282\u70b9\uff0c\u5373n~n-1\u5bf9\u5e94k+2~k+1\uff09<\/em><\/strong><\/p>\n\n\n\n<p><strong><em>\u4f46\u8981\u6ce8\u610f\uff0c\u5728\u672c\u9898\u8ba1\u7b97minDist\u6570\u7ec4\u7684\u65f6\u5019\uff0c\u57fa\u4e8e\u4e86\u672c\u6b21\u677e\u5f1b\u7684minDist\u6570\u503c\uff0c\u800c\u4e0d\u662f\u4e0a\u4e00\u6b21\u677e\u5f1b\u65f6\u7684minDist\u7684\u6570\u503c\uff0c\u6240\u4ee5\u5728\u6bcf\u6b21\u8ba1\u7b97minDist\u65f6\uff0c\u8981\u57fa\u4e8e\u5bf9\u6240\u6709\u8fb9\u4e0a\u4e00\u6b21\u677e\u5f1b\u7684minDist\u6570\u503c\u624d\u884c\uff0c\u6240\u4ee5\u6211\u4eec\u8981\u8bb0\u5f55\u4e0a\u4e00\u6b21\u677e\u5f1b\u7684minDist\uff08\u4e4b\u6240\u4ee5\u4e0e\u4e4b\u524d\u4e0d\u540c\uff0c\u662f\u56e0\u4e3a\u672c\u9898\u65e2\u53ef\u80fd\u5305\u542b\u8d1f\u6743\u56de\u8def\uff0c\u53c8\u5bf9\u7ea6\u675f\u6b21\u6570\u505a\u4e86\u9650\u5236\uff09<\/em><\/strong><\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>#include&lt;bits\/stdc++.h&gt;\nusing namespace std;\nint main() {\n    int n, m, src, dst, cnt;\n    cin &gt;&gt; n &gt;&gt; m;\n    vector&lt;vector&lt;int&gt;&gt; edges;\n    int x, y, v;\n    for(int i = 0; i &lt; m; i++) {\n        cin &gt;&gt; x &gt;&gt; y &gt;&gt; v;\n        edges.push_back({x, y, v});\n    }\n    \n    cin &gt;&gt; src &gt;&gt; dst &gt;&gt; cnt;\n    vector&lt;int&gt; minDist(n+1, INT_MAX);\n    vector&lt;int&gt; minDist_copy(n+1); \/\/\u7528\u6765\u8bb0\u5f55\u4e0a\u4e00\u6b21\u904d\u5386\u7684\u7ed3\u679c\n    minDist&#91;src] = 0;\n\n    \/\/\u677e\u5f1bcnt+1\u6b21\n    for(int k = 1; k &lt;= cnt+1; k++) {\n        minDist_copy = minDist; \/\/\u83b7\u53d6\u4e0a\u4e00\u6b21\u8ba1\u7b97\u7684\u7ed3\u679c\n        for(const vector&lt;int&gt; &amp;edge : edges) { \/\/\u904d\u5386\u6bcf\u4e00\u6761\u8fb9\n            int from = edge&#91;0];\n            int to = edge&#91;1];\n            int value = edge&#91;2];\n            \/\/\u6ce8\u610f\u4f7f\u7528minDist_copy\u6765\u8ba1\u7b97minDist \n            if(minDist_copy&#91;from] != INT_MAX &amp;&amp; minDist&#91;to] &gt; minDist_copy&#91;from] + value) {  \n                minDist&#91;to] = minDist_copy&#91;from] + value;\n            }\n        }\n    }\n    \n    if(minDist&#91;dst] == INT_MAX) cout &lt;&lt; \"unreachable\" &lt;&lt; endl;\n    else cout &lt;&lt; minDist&#91;dst] &lt;&lt; endl;\n    \n    return 0;\n}<\/code><\/pre>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h3 class=\"wp-block-heading\"><a href=\"https:\/\/kamacoder.com\/problempage.php?pid=1155\">97. \u5c0f\u660e\u901b\u516c\u56ed<\/a><\/h3>\n\n\n\n<p><em><strong>\u591a\u6e90\u6700\u77ed\u8defFloyd\u7b97\u6cd5\u6a21\u677f\u9898<\/strong><\/em><strong><em>\uff08\u6838\u5fc3\u601d\u60f3\uff1aDP\uff09<\/em><\/strong><\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>#include&lt;bits\/stdc++.h>\nusing namespace std;\nint main() {\n    int n, m, q;\n    cin >> n >> m;\n    \/\/grid&#91;i]&#91;j]&#91;k] = m\uff0c\u8868\u793a\u8282\u70b9i\u5230j\u4ee5&#91;1...k]\u96c6\u5408\u4e2d\u7684\u4e00\u4e2a\u8282\u70b9\u4e3a\u4e2d\u95f4\u8282\u70b9\u7684\u6700\u77ed\u8ddd\u79bb\u4e3am\n    \/\/\u6ce8\u610f\u4e0d\u8981\u521d\u59cb\u5316\u4e3aINT_MAX\uff0c\u56e0\u4e3a\u4e0b\u65b9\u7b97\u6cd5\u4e24\u6570\u76f8\u52a0\u65f6\u53ef\u80fd\u4f1a\u6ea2\u51fa\n    vector&lt;vector&lt;vector&lt;int>>> dp(n+1, vector&lt;vector&lt;int>>(n+1, vector&lt;int>(n+1, 10005)));\n    int x, y, v;\n    for(int i = 0; i &lt; m; i++) {\n        cin >> x >> y >> v;\n        dp&#91;x]&#91;y]&#91;0] = v;\n        dp&#91;y]&#91;x]&#91;0] = v;\n    }\n    \/\/floyd\n    for(int k = 1; k &lt;= n; k++) {\n        for(int i = 1; i &lt;= n; i++) {\n            for(int j = 1; j &lt;= n; j++) {\n                dp&#91;i]&#91;j]&#91;k] = min(dp&#91;i]&#91;j]&#91;k-1], dp&#91;i]&#91;k]&#91;k-1] + dp&#91;k]&#91;j]&#91;k-1]);\n            }\n        }\n    }\n    \n    cin >> q;\n    for(int i = 0; i &lt; q; i++) {\n        cin >> x >> y;\n        if(dp&#91;x]&#91;y]&#91;n] == 10005) cout &lt;&lt; -1 &lt;&lt; endl;\n        else cout &lt;&lt; dp&#91;x]&#91;y]&#91;n] &lt;&lt; endl; \n    }\n    \n    return 0;\n}<\/code><\/pre>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h3 class=\"wp-block-heading\"><a href=\"https:\/\/kamacoder.com\/problempage.php?pid=1203\">127. \u9a91\u58eb\u7684\u653b\u51fb<\/a><\/h3>\n\n\n\n<p><strong><em>A*\u7b97\u6cd5\uff1a\u5373\u6709\u76ee\u7684\u5730\u5e7f\u641c\uff08\u6838\u5fc3\u5728\u4e8e\u542f\u53d1\u5f0f\u51fd\u6570\uff0c\u6765<strong>\u5f71\u54cd\u961f\u5217\u91cc\u5143\u7d20\u7684\u6392\u5e8f<\/strong>\uff09<\/em><\/strong><\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>#include&lt;bits\/stdc++.h>\nusing namespace std;\nint moves&#91;1001]&#91;1001];\nint dir&#91;8]&#91;2]={-2,-1,-2,1,-1,2,1,2,2,1,2,-1,1,-2,-1,-2};\nint b1, b2;\n\/\/F = G + H\n\/\/G = \u4ece\u8d77\u70b9\u5230\u8be5\u8282\u70b9\u8def\u5f84\u6d88\u8017\n\/\/H = \u8be5\u8282\u70b9\u5230\u7ec8\u70b9\u7684\u9884\u4f30\u6d88\u8017\nstruct Knight{\n    int x,y;\n    int g,h,f;\n    bool operator &lt; (const Knight &amp; k) const{  \/\/\u91cd\u8f7d\u8fd0\u7b97\u7b26\uff0c\u4ece\u5c0f\u5230\u5927\u6392\u5e8f\n     return k.f &lt; f;\n    }\n};\n\npriority_queue&lt;Knight> que;\n\nint Heuristic(const Knight&amp; k) { \/\/\u6b27\u62c9\u8ddd\u79bb\n    return (k.x - b1) * (k.x - b1) + (k.y - b2) * (k.y - b2); \/\/\u7edf\u4e00\u4e0d\u5f00\u6839\u53f7\uff0c\u53ef\u4ee5\u63d0\u9ad8\u7cbe\u5ea6\n}\n\nvoid astar(const Knight&amp; k) {\n    Knight cur, next;\n\tque.push(k);\n\twhile(!que.empty()) {\n\t\tcur = que.top(); \n\t\tque.pop();\n\t\tif(cur.x == b1 &amp;&amp; cur.y == b2) break;\n\t\t\n\t\tfor(int i = 0; i &lt; 8; i++) {\n\t\t\tnext.x = cur.x + dir&#91;i]&#91;0];\n\t\t\tnext.y = cur.y + dir&#91;i]&#91;1];\n\t\t\tif(next.x &lt; 1 || next.x > 1000 || next.y &lt; 1 || next.y > 1000) continue;\n\t\t\tif(!moves&#91;next.x]&#91;next.y]){\n\t\t\t\tmoves&#91;next.x]&#91;next.y] = moves&#91;cur.x]&#91;cur.y] + 1;\n                \/\/ \u5f00\u59cb\u8ba1\u7b97F\n\t\t\t\tnext.g = cur.g + 5; \/\/ \u7edf\u4e00\u4e0d\u5f00\u6839\u53f7\uff0c\u8fd9\u6837\u53ef\u4ee5\u63d0\u9ad8\u7cbe\u5ea6\uff0c\u9a6c\u8d70\u65e5\uff0c1 * 1 + 2 * 2 = 5\n                next.h = Heuristic(next);\n                next.f = next.g + next.h;\n                que.push(next);\n\t\t\t}\n\t\t}\n\t}\n}\n\nint main() {\n    int n, a1, a2;\n    cin >> n;\n    while(n--) {\n        cin >> a1 >> a2 >> b1 >> b2;\n        memset(moves,0,sizeof(moves));\n        Knight start;\n        start.x = a1;\n        start.y = a2;\n        start.g = 0;\n        start.h = Heuristic(start);\n        start.f = start.g + start.h;\n\t\tastar(start);\n        while(!que.empty()) que.pop(); \/\/\u961f\u5217\u6e05\u7a7a\n\t\tcout &lt;&lt; moves&#91;b1]&#91;b2] &lt;&lt; endl;\n\t}\n\t\n\treturn 0;\n}<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"<p>More content\uff1aLeetCode hot100@\u56fe\u8bba \u5927\u7eb2 \u4ee3\u7801\u6846\u67b6 dfs bfs \u5e76\u67e5\u96c6 \u6df1\u641c\u4e0e [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[3],"tags":[27,18,19],"class_list":["post-2314","post","type-post","status-publish","format-standard","hentry","category-suanfa","tag-c","tag-leetcode","tag-19"],"_links":{"self":[{"href":"https:\/\/guapicoding.com\/index.php?rest_route=\/wp\/v2\/posts\/2314","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/guapicoding.com\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/guapicoding.com\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/guapicoding.com\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/guapicoding.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=2314"}],"version-history":[{"count":44,"href":"https:\/\/guapicoding.com\/index.php?rest_route=\/wp\/v2\/posts\/2314\/revisions"}],"predecessor-version":[{"id":2475,"href":"https:\/\/guapicoding.com\/index.php?rest_route=\/wp\/v2\/posts\/2314\/revisions\/2475"}],"wp:attachment":[{"href":"https:\/\/guapicoding.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=2314"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/guapicoding.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=2314"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/guapicoding.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=2314"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}