{"id":476,"date":"2023-04-06T11:05:35","date_gmt":"2023-04-06T03:05:35","guid":{"rendered":"https:\/\/blog.cirno.fun\/?p=476"},"modified":"2025-03-19T00:34:40","modified_gmt":"2025-03-18T16:34:40","slug":"%e5%a0%86%e4%bc%98%e5%8c%96dijkstra","status":"publish","type":"post","link":"https:\/\/blog.sssn.tech\/?p=476","title":{"rendered":"\u5806\u4f18\u5316dijkstra"},"content":{"rendered":"<p>\u9700\u8981\u524d\u7f6e\u77e5\u8bc6<a href=\"https:\/\/blog.sssn.tech\/?p=474\" title=\"\u6734\u7d20dijkstra\">\u6734\u7d20dijkstra<\/a><\/p>\n<p><img decoding=\"async\" src=\"https:\/\/blog.sssn.tech\/wp-content\/uploads\/2023\/04\/image-1680749814371.png\" alt=\"file\" \/><\/p>\n<p>\u6734\u7d20dijk\u7684\u7b97\u6cd5\u4e2d\u6709\u4e00\u4e2a\u74f6\u9888\u662f<strong>\u9009\u62e9\u51fa\u4e0d\u5728\u96c6\u5408s\u4e2d\u7684\u79bb\u8d77\u70b9\u6700\u8fd1\u7684\u70b9<\/strong><\/p>\n<p>\u5728\u6734\u7d20\u7684\u505a\u6cd5\u4e2d\uff0c\u6211\u4eec\u679a\u4e3e\u6574\u4e2ad\u6570\u7ec4\u6765\u627e\u5230\u8fd9\u4e2a\u70b9\uff0c\u5176\u5b9e\u53ef\u4ee5\u8003\u8651\u7528\u5c0f\u6839\u5806\u4f18\u5316<\/p>\n<p>\u7ef4\u62a4\u4e00\u4e2a\u5c0f\u6839\u5806\uff0c\u5176\u5143\u7d20\u662f\u4e00\u4e2a\u7ed3\u6784\u4f53\uff0c\u6210\u5458\u6709x\uff0cw\u4e24\u4e2a\uff0cx\u4ee3\u8868\u70b9\u7684\u7f16\u53f7\uff0cw\u4ee3\u8868d[x]<\/p>\n<ul>\n<li>\u6bcf\u6b21\u53d6\u51fa\u5806\u9876\u5143\u7d20\uff0c\u5982\u679c\u5df2\u7ecf\u5728\u96c6\u5408s\u4e2d\u5c31\u629b\u53bb<\/li>\n<li>\u5982\u679c\u4e0d\u5728\u96c6\u5408s\u4e2d\uff0c\u5c31\u52a0\u5165\u4e4b\uff0c\u7136\u540e\u5c1d\u8bd5\u677e\u5f1b<\/li>\n<li>\u677e\u5f1b\u6210\u529f\u7684\u70b9y\u4e0e\u677e\u5f1b\u540e\u7684d[y]\u6253\u5305\u538b\u5165\u5806\u4e2d<\/li>\n<\/ul>\n<p>\u538b\u5806\u64cd\u4f5c\u7684\u590d\u6742\u5ea6\u662flog\u7ea7\u522b\uff0c\u6240\u4ee5\u5806\u4f18\u5316dijk\u7684\u65f6\u95f4\u590d\u6742\u5ea6\u662f<\/p>\n<pre><code class=\"language-katex\">O(NlogN)<\/code><\/pre>\n<pre><code class=\"language-cpp\">#include &lt;bits\/stdc++.h&gt;\n\nusing namespace std;\n\nconst int N = 2e5 + 10, M = N;\nint n, m;\n\nint head[N], to[M], w[M], nxt[M], idx;\ninline void add(int x, int y, int z)\n{\n    to[++idx] = y;\n    w[idx] = z;\n    nxt[idx] = head[x];\n    head[x] = idx;\n}\n\nstruct node{\n    int x, w;\n    node(int x, int w): x(x), w(w){}; \/\/\u5e26\u53c2\u6784\u9020\u51fd\u6570\n    friend bool operator &gt; (const node &amp;A, const node &amp;B)\n    {\n        \/\/ \u5c0f\u6839\u5806&lt;greater&gt;\u9700\u8981\u91cd\u8f7d\u5927\u4e8e\u53f7\n        return A.w &gt; B.w;\n    }\n};\n\nint d[N];\nbool v[N];\nvoid dijk(int s)\n{\n    memset(d, 0x3f, sizeof d);\n    d[s] = 0;\n    \/\/ \u5c0f\u6839\u5806\u7684\u5b9a\u4e49\n    priority_queue&lt;node, vector&lt;node&gt;, greater&lt;node&gt; &gt; Q;\n    Q.push(node(s, 0));\n\n    while (Q.size()) \/\/ \u56e0\u4e3a\u5806\u91cc\u53ef\u80fd\u5b58\u5728s\u96c6\u5408\u4e2d\u7684\u70b9\uff0c\u9047\u5230\u8981\u8df3\u8fc7\uff0c\u6240\u4ee5\u5b9e\u9645\u5faa\u73af\u6b21\u6570\u4e0d\u786e\u5b9a\n    {\n        int x = Q.top().x;\n        Q.pop(); \/\/ \u6ce8\u610f\uff0c\u5806\u4e2d\u7684w\u53ea\u6709\u6392\u5e8f\u7684\u4f5c\u7528\uff0c\u4e0d\u9700\u8981\u53d6\u51fa\u76f4\u63a5pop\u6389\n        if (v[x]) \/\/ \u9047\u5230s\u4e2d\u7684\u70b9\u5c31\u8df3\u8fc7\n            continue;\n        v[x] = true; \/\/ \u52a0\u5165\u96c6\u5408s\n        for (int i = head[x]; i; i = nxt[i])\n        {\n            int y = to[i];\n            if (d[y] &gt; d[x] + w[i])\n            {\n                d[y] = d[x] + w[i];\n                Q.push(node(y, d[y]));\n            }\n        }\n    }\n}\n\nint main()\n{\n    cin &gt;&gt; n &gt;&gt; m;\n    for (int i = 1; i &lt;= m; i++)\n    {\n        int x, y, z;\n        cin &gt;&gt; x &gt;&gt; y &gt;&gt; z;\n        add(x, y, z);\n    }\n\n    dijk(1);\n\n    cout &lt;&lt; (d[n] == d[0] ? -1 : d[n]) &lt;&lt; endl;\n\n    return 0;\n}<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"<p>\u9700\u8981\u524d\u7f6e\u77e5\u8bc6\u6734\u7d20dijkstra \u6734\u7d20dijk\u7684\u7b97\u6cd5\u4e2d\u6709\u4e00\u4e2a\u74f6\u9888\u662f\u9009\u62e9\u51fa\u4e0d\u5728\u96c6\u5408 [&#8230;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[12,13],"tags":[],"class_list":["post-476","post","type-post","status-publish","format-standard","hentry","category-12","category-13"],"_links":{"self":[{"href":"https:\/\/blog.sssn.tech\/index.php?rest_route=\/wp\/v2\/posts\/476","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/blog.sssn.tech\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blog.sssn.tech\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blog.sssn.tech\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/blog.sssn.tech\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=476"}],"version-history":[{"count":2,"href":"https:\/\/blog.sssn.tech\/index.php?rest_route=\/wp\/v2\/posts\/476\/revisions"}],"predecessor-version":[{"id":841,"href":"https:\/\/blog.sssn.tech\/index.php?rest_route=\/wp\/v2\/posts\/476\/revisions\/841"}],"wp:attachment":[{"href":"https:\/\/blog.sssn.tech\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=476"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blog.sssn.tech\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=476"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blog.sssn.tech\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=476"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}