{"id":240,"date":"2019-08-20T10:47:02","date_gmt":"2019-08-20T02:47:02","guid":{"rendered":"https:\/\/blog.chtholly.moe\/?p=240"},"modified":"2021-08-21T18:13:28","modified_gmt":"2021-08-21T10:13:28","slug":"%e6%9c%80%e7%9f%ad%e8%b7%af","status":"publish","type":"post","link":"https:\/\/blog.sukasuka.cn\/?p=240","title":{"rendered":"\u6700\u77ed\u8def"},"content":{"rendered":"<h1>\u4e00\u3001\u5f17\u6d1b\u4f0a\u5fb7(Floyd)<\/h1>\n<pre>for(int k=1;k&lt;=n;k++)\r\n   for(int i=1;i&lt;=n;i++)\r\n       for(int j=1;j&lt;=n;j++)\r\n           sav[i][j]=min(sav[i][j],sav[i][k]+sav[k][j]);\r\n\/\/\u90bb\u63a5\u77e9\u9635\r\n\/\/O(n^3)<\/pre>\n<h1>\u4e8c\u3001\u8d1d\u5c14\u66fc-\u798f\u5fb7(Bellman-Ford)<\/h1>\n<pre>for(int j=1;j&lt;=n-1;j++)\r\n   for(int i=1;i&lt;=m;i++)\r\n      dis[v[i]]=min(dis[v[i]],dis[u[i]]+w[i]);\r\n\/\/\u5b58\u50a8\u6709\u5411\u8fb9\r\n\/\/O((n-1)*m)<\/pre>\n<h1>\u4e09\u3001Dijkstra<\/h1>\n<pre>priority_queue&lt;pair&lt;int,int&gt; &gt;q;\r\nvoid dijkstra(int s){\r\n   memset(dis,0x7f,sizeof(dis));\r\n   memset(vis,0,sizeof(vis));\r\n   q.push(make_pair(0,s);\r\n   dis[s]=0;\r\n   while(!q.empty()){\r\n        int x=q.top.second;\r\n        q.pop();\r\n        if(vis[x])continue;\r\n        vis[x]=1;\r\n        for(int i=head[x];i;i=nxt[i]){\r\n            int y=v[i],z=w[i];\r\n            if(dis[y]&gt;dis[x]+z){\r\n               dis[y]=dis[x]+z;\r\n               q.push(make_pair(-dis[y],y);\r\n            }\r\n        }\r\n   }\r\n}\r\n\/\/\u90bb\u63a5\u8868\u6751\u8fb9\r\n\/\/O((n+m)logm)<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>\u4e00\u3001\u5f17\u6d1b\u4f0a\u5fb7(Floyd) for(int k=1;k&lt;=n;k++) for(int i=1;i&#038;lt [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[2],"tags":[],"class_list":["post-240","post","type-post","status-publish","format-standard","hentry","category-cpp"],"_links":{"self":[{"href":"https:\/\/blog.sukasuka.cn\/index.php?rest_route=\/wp\/v2\/posts\/240","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/blog.sukasuka.cn\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blog.sukasuka.cn\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blog.sukasuka.cn\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/blog.sukasuka.cn\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=240"}],"version-history":[{"count":2,"href":"https:\/\/blog.sukasuka.cn\/index.php?rest_route=\/wp\/v2\/posts\/240\/revisions"}],"predecessor-version":[{"id":242,"href":"https:\/\/blog.sukasuka.cn\/index.php?rest_route=\/wp\/v2\/posts\/240\/revisions\/242"}],"wp:attachment":[{"href":"https:\/\/blog.sukasuka.cn\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=240"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blog.sukasuka.cn\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=240"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blog.sukasuka.cn\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=240"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}