{"id":534,"date":"2020-05-15T23:59:59","date_gmt":"2020-05-15T15:59:59","guid":{"rendered":"http:\/\/www.zyhcoding.club\/?p=534"},"modified":"2020-08-14T22:28:27","modified_gmt":"2020-08-14T14:28:27","slug":"dijkstra-%e5%8d%95%e6%ba%90%e6%9c%80%e7%9f%ad%e8%b7%af%e5%be%84","status":"publish","type":"post","link":"http:\/\/www.zyhcoding.club\/index.php\/2020\/05\/15\/dijkstra-%e5%8d%95%e6%ba%90%e6%9c%80%e7%9f%ad%e8%b7%af%e5%be%84\/","title":{"rendered":"Dijkstra \u5355\u6e90\u6700\u77ed\u8def\u5f84"},"content":{"rendered":"<h4><a href=\"https:\/\/www.luogu.com.cn\/problem\/P4779\">\u3010\u6a21\u677f\u3011\u5355\u6e90\u6700\u77ed\u8def\u5f84\uff08\u6807\u51c6\u7248\uff09<\/a><\/h4>\n<h6>\u6b65\u9aa4<\/h6>\n<p>\u628a\u4e00\u4e2a\u7ed3\u70b9\u548c\u5b83\u7684dist\u5c01\u88c5\u6210node\uff0c\u5efa\u7acb\u5173\u4e8enode\u7684\u4f18\u5148\u6743\u961f\u5217\uff0cdist\u5c0f\u7684\u4f18\u5148\u7ea7\u5927\u3002<br \/>\n1.\u628a\u6e90\u70b9\u5165\u961f\uff1b<br \/>\n2.\u4ece\u961f\u9996\u53d6\u51fa\u4e00\u4e2a\u5143\u7d20\uff0c\u66f4\u65b0\u5b83\u6240\u6307\u5411\u7684\u7ed3\u70b9\u7684\u6700\u77eddist\uff0c\u5e76\u628a\u66f4\u65b0\u540e\u7684\u7ed3\u70b9\u5165\u961f\uff0c\u76f4\u81f3\u961f\u7a7a\u3002<br \/>\n\u66f4\u65b0\u7ed3\u70b9\u8fd9\u4e00\u64cd\u4f5c\u4e5f\u53eb\u505a\u677e\u5f1b\u64cd\u4f5c\u3002<\/p>\n<p>\u4f18\u5148\u6743\u961f\u5217\u7684\u4f5c\u7528\uff1a\u5f53\u4e00\u4e2a\u7ed3\u70b9\u88ab\u653e\u5165\u961f\u5217\uff0c\u5e76\u4e14\u88ab\u5f53\u6210\u961f\u9996\u62ff\u51fa\u6765\u8bbf\u95ee\u8fc7\u4e00\u6b21\u4e4b\u540e\uff0c\u5b83\u7684dist\u5c31\u5df2\u7ecf\u662f\u6700\u77ed\u4e86\uff0c\u4e0d\u4f1a\u518d\u66f4\u65b0\u4e86\uff0c\u961f\u5217\u91cc\u53ef\u80fd\u8fd8\u4f1a\u6709\u8fd9\u4e2a\u70b9\uff0c\u4f46\u961f\u5217\u91cc\u73b0\u5b58\u7684\u8fd9\u4e2a\u70b9\u7684dist\u90fd\u662f\u65e7\u7684\uff0c\u800c\u4e14\u4e0d\u662f\u6700\u77ed\uff0c\u65e0\u6548\uff0c\u8bbf\u95ee\u5230\u7684\u65f6\u5019\u76f4\u63a5vis\u6807\u8bb0\u8df3\u8fc7\u5c31\u884c\u3002<br \/>\n\u8fd9\u4e2avis\u6807\u8bb0\u662f\u7528\u6765\u8fdb\u884c\u61d2\u60f0\u5220\u9664\u7684\u3002<\/p>\n<pre><code class=\"language-c++\">#include &lt;iostream&gt;\n#include &lt;vector&gt;\n#include &lt;queue&gt;\nusing namespace std;\nconst int maxn = 1e5+10, maxm = 5e5+5, inf = 2147483647;\ntypedef struct Edge{\n    int from,to,weight;\n    int next;\n}Edge;\ntypedef struct node{\n    int dist;\n    int pos;\n    bool operator &lt; (const node &amp;x) const{\n        return x.dist &lt; dist;\n    }\n}node;\nint n,m,s;\nint dist[maxn],vis[maxn];\nint head[maxn];\nint tot;\nEdge e[maxm];\npriority_queue&lt;node&gt; q;\nvoid AddEdge(int from,int to,int weight){\n    tot++;\n    e[tot].from = from;\n    e[tot].to = to;\n    e[tot].weight = weight;\n    e[tot].next = head[from];\n    head[from] = tot;\n}\nint main(){\n    int from,to,weight;\n    cin &gt;&gt; n &gt;&gt; m &gt;&gt; s;\n    for (int i=1;i&lt;=n;i++){\n        dist[i] = head[i] = inf;\n        vis[i] = 0;\n    }\n    for (int i=1;i&lt;=m;i++){\n        cin &gt;&gt; from &gt;&gt; to &gt;&gt; weight;\n        AddEdge(from,to,weight);\n    }\n    node tmp;\n    q.push((node){0,s});\n    dist[s] = 0;\n    while (!q.empty()){\n        tmp = q.top();    q.pop();\n        if (vis[tmp.pos])   continue;\n        vis[tmp.pos] = 1;\n        for (int i=head[tmp.pos];i!=inf;i=e[i].next){\n            if (dist[e[i].to] &gt; dist[tmp.pos]+e[i].weight){\n                dist[e[i].to] = dist[tmp.pos]+e[i].weight;\n                q.push((node){dist[e[i].to], e[i].to});\n            }\n        }\n    }\n    for (int i=1;i&lt;=n;i++)\n        cout &lt;&lt; dist[i] &lt;&lt; &quot; &quot;;\n    return 0;\n}<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"<p>\u3010\u6a21\u677f\u3011\u5355\u6e90\u6700\u77ed\u8def\u5f84\uff08\u6807\u51c6\u7248\uff09 \u6b65\u9aa4 \u628a\u4e00\u4e2a\u7ed3\u70b9\u548c\u5b83\u7684dist\u5c01\u88c5\u6210node\uff0c\u5efa\u7acb\u5173\u4e8enode\u7684\u4f18\u5148 [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[43],"tags":[],"_links":{"self":[{"href":"http:\/\/www.zyhcoding.club\/index.php\/wp-json\/wp\/v2\/posts\/534"}],"collection":[{"href":"http:\/\/www.zyhcoding.club\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/www.zyhcoding.club\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/www.zyhcoding.club\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/www.zyhcoding.club\/index.php\/wp-json\/wp\/v2\/comments?post=534"}],"version-history":[{"count":8,"href":"http:\/\/www.zyhcoding.club\/index.php\/wp-json\/wp\/v2\/posts\/534\/revisions"}],"predecessor-version":[{"id":791,"href":"http:\/\/www.zyhcoding.club\/index.php\/wp-json\/wp\/v2\/posts\/534\/revisions\/791"}],"wp:attachment":[{"href":"http:\/\/www.zyhcoding.club\/index.php\/wp-json\/wp\/v2\/media?parent=534"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/www.zyhcoding.club\/index.php\/wp-json\/wp\/v2\/categories?post=534"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/www.zyhcoding.club\/index.php\/wp-json\/wp\/v2\/tags?post=534"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}