{"id":243,"date":"2019-08-20T16:08:22","date_gmt":"2019-08-20T08:08:22","guid":{"rendered":"https:\/\/blog.chtholly.moe\/?p=243"},"modified":"2021-08-21T18:13:28","modified_gmt":"2021-08-21T10:13:28","slug":"%e8%b4%9f%e7%8e%af%e5%88%a4%e5%ae%9a","status":"publish","type":"post","link":"https:\/\/blog.sukasuka.cn\/?p=243","title":{"rendered":"\u8d1f\u73af\u5224\u5b9a"},"content":{"rendered":"<pre><code class=\"language-cpp\">bool bf() {\n\n    memset(dis,INF,sizeof(dis));\n\n    dis[1]=0;\n\n    for(int j=1; j&lt;=n-1; j++) {\n\n    for(int i=1; i&lt;=m; i++) {\n\n        dis[v[i]]=min(dis[v[i]],dis[u[i]]+w[i]);\n\n        if(w[i]&gt;=0)\n\n            dis[u[i]]=min(dis[u[i]],dis[v[i]]+w[i]);\/\/\u53cc\u5411\u8fb9\n\n            }\n\n    }\n    \/\/\u591a\u4e00\u6b21\u677e\u5f1b\n    for(int i=1; i&lt;=m; i++) {\n\n        if(dis[u[i]]!=INF&amp;&amp;dis[v[i]]&gt;dis[u[i]]+w[i])return 1;\n\n        if(w[i]&gt;=0) {\n\n            if(dis[v[i]]!=0x7f&amp;&amp;dis[u[i]]&gt;dis[v[i]]+w[i])return 1;\/\/\u53cc\u5411\u8fb9\n\n            }\n\n    }\n\n    return 0;\n\n}<\/code><\/pre>\n<p>2020.8.26 UPDATE<\/p>\n<pre><code class=\"language-cpp\">vector&lt;pair&lt;int,int&gt; &gt;G[50003];\nstruct SPFA_WITH_NEG_CIRC {\n    const static int MAXN = 50000;\n    int dis[MAXN+5],dpt[MAXN+5];\n    bool vis[MAXN+5];\n    bool spfa(int S,bool cir=0) {\n        for(int i=0; i&lt;=n; i++)dis[i]=0x7ffffff,vis[i]=dpt[i]=0;\n        dis[S]=0;\n        deque&lt;int&gt;q;\n        q.push_back(S);\n        while(!q.empty()) {\n            int x=q.front();\n            q.pop_front();\n            vis[x]=0;\n            int sz=G[x].size();\n            for(int i=0; i&lt;sz; i++) {\n                int y=G[x][i].first,w=G[x][i].second;\n                if(dis[y]&gt;dis[x]+w) {\n                    dis[y]=dis[x]+w;\n                    if(!vis[y]) {\n                        vis[y]=1;\n                        if(cir&amp;&amp;++dpt[y]&gt;=n)return 1;\n                        if(cir)q.push_back(y);\n                    }\n                }\n            }\n        }\n        return 0;\n    }\n} T;<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"<p>bool bf() { memset(dis,INF,sizeof(dis)); dis[1]=0; for( [&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-243","post","type-post","status-publish","format-standard","hentry","category-cpp"],"_links":{"self":[{"href":"https:\/\/blog.sukasuka.cn\/index.php?rest_route=\/wp\/v2\/posts\/243","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=243"}],"version-history":[{"count":2,"href":"https:\/\/blog.sukasuka.cn\/index.php?rest_route=\/wp\/v2\/posts\/243\/revisions"}],"predecessor-version":[{"id":461,"href":"https:\/\/blog.sukasuka.cn\/index.php?rest_route=\/wp\/v2\/posts\/243\/revisions\/461"}],"wp:attachment":[{"href":"https:\/\/blog.sukasuka.cn\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=243"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blog.sukasuka.cn\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=243"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blog.sukasuka.cn\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=243"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}