{"id":51,"date":"2026-02-23T14:15:08","date_gmt":"2026-02-23T06:15:08","guid":{"rendered":"https:\/\/blog.mirpri.com\/?p=51"},"modified":"2026-02-23T16:05:46","modified_gmt":"2026-02-23T08:05:46","slug":"luogu-p5960","status":"publish","type":"post","link":"https:\/\/blog.mirpri.com\/index.php\/luogu-p5960\/","title":{"rendered":"P5960 \u3010\u6a21\u677f\u3011\u5dee\u5206\u7ea6\u675f"},"content":{"rendered":"\n<h2 class=\"wp-block-heading\">\u9898\u76ee\u63cf\u8ff0<\/h2>\n\n\n\n<p>\u7ed9\u51fa\u4e00\u7ec4\u5305\u542b m \u4e2a\u4e0d\u7b49\u5f0f\uff0c\u6709 n \u4e2a\u672a\u77e5\u6570\u7684\u5f62\u5982\uff1a<\/p>\n\n\n\n<div class=\"wp-block-math\"><math display=\"block\"><semantics><mrow><mo fence=\"true\" form=\"prefix\">{<\/mo><mtable><mtr><mtd class=\"tml-left\" style=\"padding-left:0em;padding-right:0em;\"><mrow><msub><mi>x<\/mi><msub><mi>c<\/mi><mn>1<\/mn><\/msub><\/msub><mo>\u2212<\/mo><msub><mi>x<\/mi><msubsup><mi>c<\/mi><mn>1<\/mn><mo lspace=\"0em\" rspace=\"0em\" class=\"tml-prime\">\u2032<\/mo><\/msubsup><\/msub><mo>\u2264<\/mo><msub><mi>y<\/mi><mn>1<\/mn><\/msub><\/mrow><\/mtd><\/mtr><mtr><mtd class=\"tml-left\" style=\"padding-left:0em;padding-right:0em;\"><mrow><msub><mi>x<\/mi><msub><mi>c<\/mi><mn>2<\/mn><\/msub><\/msub><mo>\u2212<\/mo><msub><mi>x<\/mi><msubsup><mi>c<\/mi><mn>2<\/mn><mo lspace=\"0em\" rspace=\"0em\" class=\"tml-prime\">\u2032<\/mo><\/msubsup><\/msub><mo>\u2264<\/mo><msub><mi>y<\/mi><mn>2<\/mn><\/msub><\/mrow><\/mtd><\/mtr><mtr><mtd class=\"tml-left\" style=\"padding-left:0em;padding-right:0em;\"><mo>\u22ef<\/mo><\/mtd><\/mtr><mtr><mtd class=\"tml-left\" style=\"padding-left:0em;padding-right:0em;\"><mrow><msub><mi>x<\/mi><msub><mi>c<\/mi><mi>m<\/mi><\/msub><\/msub><mo>\u2212<\/mo><msub><mi>x<\/mi><msubsup><mi>c<\/mi><mi>m<\/mi><mo lspace=\"0em\" rspace=\"0em\" class=\"tml-prime\">\u2032<\/mo><\/msubsup><\/msub><mo>\u2264<\/mo><msub><mi>y<\/mi><mi>m<\/mi><\/msub><\/mrow><\/mtd><\/mtr><\/mtable><mo fence=\"true\" form=\"postfix\"><\/mo><\/mrow><annotation encoding=\"application\/x-tex\"> \\begin{cases}\nx_{c_1}-x_{c&#8217;_1}\\leq y_1 \\\\\nx_{c_2}-x_{c&#8217;_2} \\leq y_2 \\\\\n\\cdots \\\\\nx_{c_m} &#8211; x_{c&#8217;_m}\\leq y_m\n\\end{cases}<\/annotation><\/semantics><\/math><\/div>\n\n\n\n<p>\u7684\u4e0d\u7b49\u5f0f\u7ec4\uff0c\u6c42\u4efb\u610f\u4e00\u7ec4\u6ee1\u8db3\u8fd9\u4e2a\u4e0d\u7b49\u5f0f\u7ec4\u7684\u89e3\u3002<\/p>\n\n\n<a class=\"wp-block-read-more\" href=\"https:\/\/blog.mirpri.com\/index.php\/luogu-p5960\/\" target=\"_self\">Read more<span class=\"screen-reader-text\">: P5960 \u3010\u6a21\u677f\u3011\u5dee\u5206\u7ea6\u675f<\/span><\/a>\n\n\n<h2 class=\"wp-block-heading\">\u89e3\u7b54<\/h2>\n\n\n\n<p>\u5dee\u5206\u7ea6\u675f\u95ee\u9898\u7684\u6838\u5fc3\u662f<strong>\u5c06\u4e0d\u7b49\u5f0f\u8f6c\u5316\u4e3a\u56fe\u8bba\u4e2d\u7684\u8fb9\uff0c\u7136\u540e\u901a\u8fc7\u6c42\u5355\u6e90\u6700\u77ed\u8def\u6765\u6c42\u89e3<\/strong>\uff1a<\/p>\n\n\n\n<ol class=\"wp-block-list\">\n<li><strong>\u4e0d\u7b49\u5f0f\u8f6c\u5316<\/strong>\uff1a\u628a<math data-latex=\"x_c\u200b\u2212x_{c\u2032}\u200b\u2264y\"><semantics><mrow><msub><mi>x<\/mi><mi>c<\/mi><\/msub><mtext>\u200b<\/mtext><mo>\u2212<\/mo><msub><mi>x<\/mi><mrow><mi>c<\/mi><mtext>\u2032<\/mtext><\/mrow><\/msub><mtext>\u200b<\/mtext><mo>\u2264<\/mo><mi>y<\/mi><\/mrow><annotation encoding=\"application\/x-tex\">x_c\u200b\u2212x_{c\u2032}\u200b\u2264y<\/annotation><\/semantics><\/math>\u53d8\u5f62\u4e3a<math data-latex=\"x_c\u200b\u2264x_{c\u2032}\u200b+y\"><semantics><mrow><msub><mi>x<\/mi><mi>c<\/mi><\/msub><mtext>\u200b<\/mtext><mo>\u2264<\/mo><msub><mi>x<\/mi><mrow><mi>c<\/mi><mtext>\u2032<\/mtext><\/mrow><\/msub><mtext>\u200b<\/mtext><mo>+<\/mo><mi>y<\/mi><\/mrow><annotation encoding=\"application\/x-tex\">x_c\u200b\u2264x_{c\u2032}\u200b+y<\/annotation><\/semantics><\/math>\uff0c\u8fd9\u5bf9\u5e94\u56fe\u4e2d\u4ece\u8282\u70b9c\u2032\u5230c\u7684\u4e00\u6761\u6709\u5411\u8fb9\uff0c\u8fb9\u6743\u4e3ay\u3002<\/li>\n\n\n\n<li><strong>\u865a\u62df\u6e90\u70b9<\/strong>\uff1a\u4e3a\u4e86\u4fdd\u8bc1\u56fe\u7684\u8fde\u901a\u6027\uff08\u6240\u6709\u8282\u70b9\u90fd\u80fd\u88ab\u904d\u5386\u5230\uff09\uff0c\u65b0\u589e\u4e00\u4e2a\u865a\u62df\u6e90\u70b90\uff0c\u5411\u6240\u6709\u8282\u70b91\u223cn\u8fde\u4e00\u6761\u8fb9\u6743\u4e3a0\u7684\u8fb9\uff08\u5373xi\u200b\u2264x0\u200b+0\uff0c\u7b49\u4ef7\u4e8exi\u200b\u22640\uff0c\u4e0d\u5f71\u54cd\u539f\u4e0d\u7b49\u5f0f\u7ec4\u7684\u89e3\uff09\u3002<\/li>\n\n\n\n<li><strong>\u5224\u73af\u4e0e\u6c42\u89e3<\/strong>\uff1a\u4ece\u865a\u62df\u6e90\u70b90\u51fa\u53d1\u6c42\u5355\u6e90\u6700\u77ed\u8def\uff1a\n<ul class=\"wp-block-list\">\n<li>\u82e5\u56fe\u4e2d\u5b58\u5728<strong>\u8d1f\u6743\u56de\u8def<\/strong>\uff0c\u8bf4\u660e\u4e0d\u7b49\u5f0f\u7ec4\u65e0\u89e3\uff1b<\/li>\n\n\n\n<li>\u82e5\u65e0\u8d1f\u6743\u56de\u8def\uff0c\u5219\u6bcf\u4e2a\u8282\u70b9\u7684\u6700\u77ed\u8def\u503c\u5c31\u662f\u4e00\u7ec4\u53ef\u884c\u89e3\u3002<\/li>\n<\/ul>\n<\/li>\n<\/ol>\n\n\n\n<p>\u6c42\u89e3\u6700\u77ed\u8def\u65f6\uff0c\u8981\u6c42\u80fd\u591f\u5224\u65ad\u8d1f\u73af\uff0c\u4f7f\u7528 Bellman-Ford \u6216 SPFA \u7b97\u6cd5\u3002<\/p>\n\n\n\n<h3 class=\"wp-block-heading\">Bellman-Ford<\/h3>\n\n\n\n<p><strong>\u521d\u59cb\u5316<\/strong>\uff1a\u5148\u7ed9\u6240\u6709\u8282\u70b9\u7684 \u201c\u5f53\u524d\u6700\u77ed\u8def\u5f84\u201d\uff08<code>dist[i]<\/code>\uff09 \u8d4b\u503c\u4e3a \u201c\u65e0\u7a77\u5927\u201d\uff0c\u53ea\u6709\u6e90\u70b9\u7684\u6700\u77ed\u8def\u5f84\u8bbe\u4e3a 0\uff08\u81ea\u5df1\u5230\u81ea\u5df1\u8ddd\u79bb\u4e3a 0\uff09\u3002 <\/p>\n\n\n\n<p><strong>\u591a\u8f6e\u677e\u5f1b\u66f4\u65b0<\/strong>\uff1a<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>\u8fdb\u884c <code>n-1<\/code> \u8f6e\u66f4\u65b0\uff08\u79f0\u4e3a \u201c\u677e\u5f1b\u201d\uff0cn\u4e3a\u8282\u70b9\u603b\u6570\uff09\uff1b<\/li>\n\n\n\n<li>\u6bcf\u4e00\u8f6e\u90fd\u904d\u5386\u56fe\u4e2d<strong>\u6240\u6709\u7684\u8fb9<\/strong>\uff1a\u5bf9\u6bcf\u6761\u8fb9\uff08\u8bbe\u4ece\u8282\u70b9 A \u5230 B\uff0c\u8fb9\u6743\u4e3a W\uff09\uff0c\u68c0\u67e5 \u201c\u4ece\u6e90\u70b9\u5230 A \u7684\u6700\u77ed\u8def\u5f84 + W\u201d \u662f\u5426\u6bd4 \u201c\u5f53\u524d\u8bb0\u5f55\u7684\u6e90\u70b9\u5230 B \u7684\u6700\u77ed\u8def\u5f84\u201d \u66f4\u77ed\uff1b\u5982\u679c\u662f\uff0c\u5c31\u66f4\u65b0 B \u7684\u6700\u77ed\u8def\u5f84\u3002<\/li>\n\n\n\n<li>\u4f18\u5316\u70b9\uff1a\u5982\u679c\u67d0\u4e00\u8f6e\u904d\u5386\u5b8c\u6240\u6709\u8fb9\u540e\uff0c\u6ca1\u6709\u4efb\u4f55\u8282\u70b9\u7684\u6700\u77ed\u8def\u5f84\u88ab\u66f4\u65b0\uff0c\u8bf4\u660e\u6240\u6709\u6700\u77ed\u8def\u5df2\u7ecf\u627e\u5230\uff0c\u53ef\u4ee5\u63d0\u524d\u7ed3\u675f\uff0c\u4e0d\u7528\u8d70\u5b8c <code>n-1<\/code> \u8f6e\u3002<\/li>\n<\/ul>\n\n\n\n<p><strong>\u68c0\u6d4b\u8d1f\u6743\u56de\u8def<\/strong>\uff1a<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>\u5b8c\u6210 <code>\u8282\u70b9\u603b\u6570-1<\/code> \u8f6e\u66f4\u65b0\u540e\uff0c\u518d\u989d\u5916\u904d\u5386\u4e00\u6b21\u6240\u6709\u8fb9\uff1b<\/li>\n\n\n\n<li>\u5982\u679c\u8fd9\u4e00\u8f6e\u8fd8\u80fd\u66f4\u65b0\u67d0\u4e2a\u8282\u70b9\u7684\u6700\u77ed\u8def\u5f84\uff0c\u8bf4\u660e\u5b58\u5728\u8d1f\u6743\u56de\u8def\uff08\u56e0\u4e3a\u6b63\u5e38\u60c5\u51b5\u4e0b\uff0c<code>n-1<\/code> \u8f6e\u5df2\u7ecf\u80fd\u627e\u5230\u6240\u6709\u6700\u77ed\u8def\uff0c\u8fd8\u80fd\u66f4\u65b0\u5c31\u610f\u5473\u7740\u5b58\u5728\u8d1f\u73af\uff09\u3002<\/li>\n<\/ul>\n\n\n\n<h3 class=\"wp-block-heading\">SPFA<\/h3>\n\n\n\n<p>Bellman-Ford\u7b97\u6cd5\u7684\u4f18\u5316\u3002<\/p>\n\n\n\n<p>Bellman-Ford \u6548\u7387\u4f4e\u7684\u5173\u952e\u662f \u201c\u6bcf\u8f6e\u904d\u5386\u6240\u6709\u8fb9\u201d\uff0c\u4f46\u5b9e\u9645\u4e0a\uff1a<strong>\u53ea\u6709\u67d0\u4e2a\u8282\u70b9\u7684\u6700\u77ed\u8def\u5f84\u88ab\u66f4\u65b0\u540e\uff0c\u4ee5\u8fd9\u4e2a\u8282\u70b9\u4e3a\u8d77\u70b9\u7684\u8fb9\uff0c\u624d\u6709\u53ef\u80fd\u66f4\u65b0\u5b83\u7684\u90bb\u63a5\u8282\u70b9\u7684\u6700\u77ed\u8def\u5f84<\/strong>\u3002<\/p>\n\n\n\n<p>SPFA \u5c31\u662f\u6293\u4f4f\u8fd9\u4e2a\u7279\u70b9\uff0c\u7528 \u201c\u961f\u5217\u201d \u8bb0\u5f55 \u201c\u521a\u521a\u88ab\u66f4\u65b0\u8fc7\u6700\u77ed\u8def\u5f84\u7684\u8282\u70b9\u201d\uff0c\u53ea\u5904\u7406\u8fd9\u4e9b\u8282\u70b9\u7684\u51fa\u8fb9\uff0c\u907f\u514d\u904d\u5386\u65e0\u7528\u7684\u8fb9\u3002<\/p>\n\n\n\n<h2 class=\"wp-block-heading\">AC\u4ee3\u7801<\/h2>\n\n\n\n<pre class=\"wp-block-code\"><code>#include &lt;iostream>\n#include &lt;vector>\n#include &lt;unordered_set>\n\nusing namespace std;\n\nconst int mm=5050;\nint n,m;\nvector&lt;pair&lt;int,int>> e&#91;mm];\nint dist&#91;mm];\n\nbool SPFA(){\n    for (int i=1; i&lt;=n; i++) {\n        dist&#91;i]=1e8;\n    }\n    \n    unordered_set&lt;int> q;\n\n    q.insert(0);\n    for (int i=0; i&lt;n+1; i++) {\n        if (q.empty()) break;\n        unordered_set&lt;int> newq;\n        for (int j : q) {\n            for (auto k : e&#91;j]) {\n                int newdist=dist&#91;j]+k.second;\n                if(dist&#91;k.first]>newdist){\n                    dist&#91;k.first]=newdist;\n                    newq.insert(k.first);\n                }\n            }\n        }\n        q=std::move(newq);\n    }\n\n    if (!q.empty()){\n        return false;\n    }\n    return true;\n}\n\nint main(){\n    cin>>n>>m;\n    for (int i=0; i&lt;m; i++) {\n        int c, c1, y;\n        cin>>c>>c1>>y;\n        e&#91;c1].push_back(make_pair(c, y));\n    }\n\n    for (int i=1; i&lt;=n; i++) {\n        e&#91;0].push_back(make_pair(i, 0));\n    }\n\n    if (SPFA()){\n        for (int i=1; i&lt;=n; i++) {\n        cout&lt;&lt;dist&#91;i]&lt;&lt;' ';\n        }\n    } else {\n        cout&lt;&lt;\"NO\";\n    }\n\n    return 0;\n}<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"<p>\u9898\u76ee\u63cf\u8ff0 \u7ed9\u51fa\u4e00\u7ec4\u5305\u542b m \u4e2a\u4e0d\u7b49\u5f0f\uff0c\u6709 n \u4e2a\u672a\u77e5\u6570\u7684\u5f62\u5982\uff1a \u7684\u4e0d\u7b49\u5f0f\u7ec4\uff0c\u6c42\u4efb\u610f\u4e00\u7ec4\u6ee1\u8db3\u8fd9\u4e2a\u4e0d\u7b49\u5f0f\u7ec4\u7684\u89e3\u3002 \u89e3\u7b54 \u5dee\u5206\u7ea6\u675f\u95ee\u9898\u7684\u6838\u5fc3\u662f\u5c06\u4e0d\u7b49\u5f0f\u8f6c\u5316\u4e3a\u56fe\u8bba\u4e2d\u7684\u8fb9\uff0c\u7136\u540e\u901a\u8fc7\u6c42\u5355\u6e90\u6700\u77ed\u8def\u6765\u6c42\u89e3\uff1a \u6c42\u89e3\u6700\u77ed\u8def\u65f6\uff0c\u8981\u6c42\u80fd\u591f\u5224\u65ad\u8d1f\u73af\uff0c\u4f7f\u7528 Bellman-Ford \u6216 SPFA \u7b97\u6cd5\u3002 Bellman-Ford \u521d\u59cb\u5316\uff1a\u5148\u7ed9\u6240\u6709\u8282\u70b9\u7684 \u201c\u5f53\u524d\u6700\u77ed\u8def\u5f84\u201d\uff08dist[i]\uff09 \u8d4b\u503c\u4e3a \u201c\u65e0\u7a77\u5927\u201d\uff0c\u53ea\u6709\u6e90\u70b9\u7684\u6700\u77ed\u8def\u5f84\u8bbe\u4e3a 0\uff08\u81ea\u5df1\u5230\u81ea\u5df1\u8ddd\u79bb\u4e3a 0\uff09\u3002 \u591a\u8f6e\u677e\u5f1b\u66f4\u65b0\uff1a \u68c0\u6d4b\u8d1f\u6743\u56de\u8def\uff1a SPFA Bellman-Ford\u7b97\u6cd5\u7684\u4f18\u5316\u3002 Bellman-Ford \u6548\u7387\u4f4e\u7684\u5173\u952e\u662f \u201c\u6bcf\u8f6e\u904d\u5386\u6240\u6709\u8fb9\u201d\uff0c\u4f46\u5b9e\u9645\u4e0a\uff1a\u53ea\u6709\u67d0\u4e2a\u8282\u70b9\u7684\u6700\u77ed\u8def\u5f84\u88ab\u66f4\u65b0\u540e\uff0c\u4ee5\u8fd9\u4e2a\u8282\u70b9\u4e3a\u8d77\u70b9\u7684\u8fb9\uff0c\u624d\u6709\u53ef\u80fd\u66f4\u65b0\u5b83\u7684\u90bb\u63a5\u8282\u70b9\u7684\u6700\u77ed\u8def\u5f84\u3002 SPFA \u5c31\u662f\u6293\u4f4f\u8fd9\u4e2a\u7279\u70b9\uff0c\u7528 \u201c\u961f\u5217\u201d \u8bb0\u5f55 \u201c\u521a\u521a\u88ab\u66f4\u65b0\u8fc7\u6700\u77ed\u8def\u5f84\u7684\u8282\u70b9\u201d\uff0c\u53ea\u5904\u7406\u8fd9\u4e9b\u8282\u70b9\u7684\u51fa\u8fb9\uff0c\u907f\u514d\u904d\u5386\u65e0\u7528\u7684\u8fb9\u3002 AC\u4ee3\u7801<\/p>\n","protected":false},"author":4,"featured_media":43,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[8],"tags":[],"class_list":["post-51","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-algorithm"],"_links":{"self":[{"href":"https:\/\/blog.mirpri.com\/index.php\/wp-json\/wp\/v2\/posts\/51","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/blog.mirpri.com\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blog.mirpri.com\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blog.mirpri.com\/index.php\/wp-json\/wp\/v2\/users\/4"}],"replies":[{"embeddable":true,"href":"https:\/\/blog.mirpri.com\/index.php\/wp-json\/wp\/v2\/comments?post=51"}],"version-history":[{"count":0,"href":"https:\/\/blog.mirpri.com\/index.php\/wp-json\/wp\/v2\/posts\/51\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/blog.mirpri.com\/index.php\/wp-json\/wp\/v2\/media\/43"}],"wp:attachment":[{"href":"https:\/\/blog.mirpri.com\/index.php\/wp-json\/wp\/v2\/media?parent=51"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blog.mirpri.com\/index.php\/wp-json\/wp\/v2\/categories?post=51"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blog.mirpri.com\/index.php\/wp-json\/wp\/v2\/tags?post=51"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}