{"id":19,"date":"2022-11-19T12:02:20","date_gmt":"2022-11-19T04:02:20","guid":{"rendered":"https:\/\/zqy.ac.cn\/?p=19"},"modified":"2022-11-19T20:36:55","modified_gmt":"2022-11-19T12:36:55","slug":"floyd","status":"publish","type":"post","link":"https:\/\/acosx.top\/?p=19","title":{"rendered":"Floyd"},"content":{"rendered":"<p>Floyd \u662f\u4e00\u4e2a\u591a\u6e90\u6700\u77ed\u8def\u7b97\u6cd5\u3002<br \/>\n<img decoding=\"async\" src=\"https:\/\/acosx.top\/wp-content\/uploads\/2022\/11\/image-1668830109200.png\" alt=\"file\" \/><\/p>\n<p><img decoding=\"async\" src=\"https:\/\/acosx.top\/wp-content\/uploads\/2022\/11\/image-1668830430013.png\" alt=\"file\" \/><\/p>\n<p><strong>\u8f93\u5165\u6837\u4f8b\uff1a<\/strong><\/p>\n<pre><code>3 3 2\n1 2 1\n2 3 2\n1 3 1\n2 1\n1 3<\/code><\/pre>\n<p><strong>\u8f93\u51fa\u6837\u4f8b\uff1a<\/strong><\/p>\n<pre><code>impossible\n1<\/code><\/pre>\n<pre><code class=\"language-cpp\">\/\/ AcWing 805\n#include&lt;bits\/stdc++.h&gt;\nusing namespace std;\n\nint dp[205][205];\nconst int INF = 1e9; \/\/ \u4e0d\u8981\u4f7f\u7528INT_MAX \u5c06\u5bfc\u81f4\u6ea2\u51fa\nint n,m,k,x,y,z;\n\nvoid floyd(){\n    for(int k = 1;k &lt;= n;k++){ \/\/ \u6ce8\u610f\u5148\u679a\u4e3ek\n        for(int i = 1;i &lt;= n;i++){\n            for(int j = 1;j &lt;= n;j++){\n                dp[i][j] = min(dp[i][j],dp[i][k] + dp[k][j]); \/\/ \u72b6\u6001\u8f6c\u79fb\u65b9\u7a0b\n            }\n        }\n    }\n}\n\nint main(){\n    cin&gt;&gt;n&gt;&gt;m&gt;&gt;k;\n    \/\/ \u521d\u59cb\u5316\n    for(int i = 1;i &lt;= n;i++){\n        for(int j = 1;j &lt;= n;j++){\n            if(i == j)dp[i][j] = 0;\n            else dp[i][j] = INF;\n        }\n    }\n\n    \/\/ \u8f93\u5165x,y,z\n    for(int i = 1;i &lt;= m;i++){\n        cin&gt;&gt;x&gt;&gt;y&gt;&gt;z;\n        dp[x][y] = min(dp[x][y],z);\n    }\n\n    floyd();\n\n    for(int i = 1;i &lt;= k;i++){\n        cin&gt;&gt;x&gt;&gt;y;\n        if(dp[x][y] &gt; INF\/2)cout&lt;&lt;&quot;impossible&quot;&lt;&lt;endl; \/\/\u7531\u4e8e\u6709\u8d1f\u6743\u8fb9\u5b58\u5728\u6240\u4ee5\u7ea6\u5927\u8fc7INF\/2\u4e5f\u5f88\u5408\u7406\n        else cout&lt;&lt;dp[x][y]&lt;&lt;endl; \/\/ \u76f4\u63a5\u8f93\u51fadp[x][y]\u5373\u53ef\n    }\n    return 0;\n}<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"<p>Floyd \u662f\u4e00\u4e2a\u591a\u6e90\u6700\u77ed\u8def\u7b97\u6cd5\u3002 \u8f93\u5165\u6837\u4f8b\uff1a 3 3 2 1 2 1 2 3 2 1 3 1 2 1 1 3&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_kadence_starter_templates_imported_post":false,"_kad_post_transparent":"","_kad_post_title":"","_kad_post_layout":"","_kad_post_sidebar_id":"","_kad_post_content_style":"","_kad_post_vertical_padding":"","_kad_post_feature":"","_kad_post_feature_position":"","_kad_post_header":false,"_kad_post_footer":false,"_kad_post_classname":"","footnotes":""},"categories":[1],"tags":[],"class_list":["post-19","post","type-post","status-publish","format-standard","hentry","category-uncategorized"],"_links":{"self":[{"href":"https:\/\/acosx.top\/index.php?rest_route=\/wp\/v2\/posts\/19","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/acosx.top\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/acosx.top\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/acosx.top\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/acosx.top\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=19"}],"version-history":[{"count":0,"href":"https:\/\/acosx.top\/index.php?rest_route=\/wp\/v2\/posts\/19\/revisions"}],"wp:attachment":[{"href":"https:\/\/acosx.top\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=19"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/acosx.top\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=19"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/acosx.top\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=19"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}