{"id":1125,"date":"2024-08-24T09:00:00","date_gmt":"2024-08-24T01:00:00","guid":{"rendered":"https:\/\/seanxd.com\/?p=1125"},"modified":"2024-07-25T01:00:33","modified_gmt":"2024-07-24T17:00:33","slug":"zerojudge-e810","status":"publish","type":"post","link":"https:\/\/seanxd.com\/zh\/zerojudge-e810\/","title":{"rendered":"ZeroJudge E810: \u6f5b\u6c34"},"content":{"rendered":"\n\n\n

\u5c0f\u8ed2\u662f\u4e00\u500b\u71b1\u611b\u6f5b\u6c34\u7684\u4eba\uff0c\u4ed6\u8d81\u8457\u653e\u6691\u5047\u7684\u6642\u9593\u53bb\u6f8e\u6e56\u6f5b\u6c34\u3002\u6f8e\u6e56\u7531\u8a31\u591a\u5c0f\u5cf6\u7d44\u6210\uff0c\u5c0f\u8ed2\u4eca\u5929\u60f3\u5f9e A \u5cf6\u7d93\u7531\u6f5b\u6c34\u7684\u65b9\u5f0f\u5230 B \u5cf6\u3002\u6f5b\u6c34\u9700\u8981\u80cc\u8457\u6c27\u6c23\u7b52\uff0c\u800c \u5c0f\u8ed2\u4e0d\u60f3\u6d6a\u8cbb\u529b\u6c23\u53bb\u80cc\u904e\u91cd\u7684\u6c27\u6c23\u7b52\uff0c\u4ed6\u5e0c\u671b\u6c27\u6c23\u7b52\u7684\u5bb9\u91cf\u5920\u7528\u5c31\u597d\u3002\u5c0f\u5cf6\u9593\u7684\u8ddd\u96e2\u6709\u9577\u6709\u77ed\uff0c\u9700\u8981\u82b1\u8cbb\u7684\u6c27\u6c23\u91cf\u4e5f\u4e0d\u540c\uff0c\u4f46\u6709\u4e9b\u5cf6\u4e4b\u9593\u4e0d\u80fd\u7531\u6f5b\u6c34\u4f86\u79fb\u52d5\uff1b\u6bcf\u62b5\u9054\u4e00\u5ea7\u5cf6\u5c31\u53ef\u4ee5\u628a\u6c27\u6c23\u7b52\u91cd\u65b0\u88dd\u6eff\u3002\u8acb\u4f60\u5e6b\u5c0f\u8ed2\u7b97\u51fa\u4ed6\u6700\u5c11\u8981\u80cc\u591a\u5c11\u5bb9\u91cf\u7684\u6c27\u6c23\u7b52\u624d\u80fd\u8b93\u4ed6\u9806\u5229\u5f9e A \u5cf6\u6f5b\u6c34\u62b5\u9054 B \u5cf6\u3002<\/p>\n\n\n\n

\u7bc4\u4f8b\u6e2c\u8cc7<\/h2>\n\n\n\n
\u7bc4\u4f8b\u8f38\u5165<\/th>\u7bc4\u4f8b\u8f38\u51fa<\/th><\/tr><\/thead>
\u7b2c\u4e00\u5217\u6709\u5169\u500b\u6574\u6578 N \u8207 M\uff082 <= N <= 500\u30010 <= M <= N*(N-1)\/2\uff09\uff0c\u4ee3\u8868\u6709 N \u5ea7\u5c0f \u5cf6\u4ee5\u53ca M \u689d\u6f5b\u6c34\u8def\u5f91\uff0c\u5c0f\u5cf6\u7684\u7de8\u865f\u70ba 0\uff5eN-1\u3002\u63a5\u4e0b\u53bb\u6709 M \u5217\uff0c\u4ee3\u8868\u5cf6\u8207\u5cf6\u4e4b\u9593\u79fb\u52d5\u6240\u9700\u82b1\u8cbb\u7684\u6c27\u6c23\u91cf\uff1b\u6bcf\u5217\u6709\u4e09\u500b\u6574\u6578\uff0c\u524d\u5169\u500b\u6574\u6578\u70ba\u5cf6\u7684\u7de8\u865f\uff0c\u7b2c\u4e09\u500b\u6574\u6578\u70ba\u5169\u500b\u5cf6\u4e4b\u9593\u6f5b\u6c34\u79fb\u52d5\u9700\u8981\u7684\u6c27\u6c23\u91cf W (2 <= W <= 50000)\uff0c\u96d9\u5411\u6240\u9700\u8981\u7684\u6c27\u6c23\u91cf\u76f8\u7b49\u3002\u6700\u5f8c\u4e00\u5217\u6709\u5169\u500b\u6574\u6578 A \u8207 B\uff0c\u4ee3\u8868\u5c0f\u8ed2\u60f3\u5f9e A \u5cf6\u6f5b\u6c34\u79fb\u52d5\u5230 B \u5cf6\u3002<\/td>\u8acb\u8f38\u51fa\u5c0f\u8ed2\u6700\u5c11\u8981\u80cc\u591a\u5c11\u5bb9\u91cf\u7684\u6c27\u6c23\u7b52\uff0c\u82e5\u5f9e A \u5cf6\u7121\u6cd5\u7d93\u7531\u6f5b\u6c34\u79fb\u52d5\u5230 B \u5cf6\uff0c\u8acb\u8f38\u51fa -1\u3002<\/td><\/tr>
4 4
0 2 3
0 1 1
1 3 6
2 3 5
0 3<\/td>		5<\/td><\/tr>
5 6
0 1 1
0 2 2
1 3 4
3 2 5
4 2 6
3 4 7
0 4<\/td>		6<\/td><\/tr>
5 5
0 1 5
1 2 6
2 3 2
3 1 4
2 0 3
1 4<\/td>		-1<\/td><\/tr><\/tbody><\/table>
ZeroJudge E810 \u7bc4\u4f8b\u6e2c\u8cc7<\/figcaption><\/figure>\n\n\n\n

\u89e3\u984c\u601d\u8def<\/h2>\n\n\n\n

\u5ba3\u544a\u4e00\u500b Map<int, vector<pair<int, int>>> \u4f86\u5b58\u8cc7\u6599\uff0cpair \u4e2d\u7684 second \u662f\u7528\u4f86\u5b58 W \u7528\u7684\u3002\u5ba3\u544a\u4e00\u500b ans \u8b8a\u6578\u9810\u8a2d\u70ba 999999\uff0c\u9084\u6709\u4e00\u500b\u9663\u5217 point[1000] \u88e1\u9762\u5f9e 0 \u5230 N-1 \u9810\u8a2d\u4e5f\u662f 999999\uff0c\u4f46\u662f\u8981\u5c07\u7b2c A \u500b\u4f4d\u7f6e\u7684 point \u8a2d\u70ba 0\u3002<\/p>\n\n\n\n

\u8dd1 BFS\uff0c\u6bcf\u4e00\u6b21\u5c31\u662f\u5224\u65b7\u8d77\u9ede\u4e2d\u7684\u9ede\u7684\u4e0b\u4e00\u4e9b\u9ede\u6709\u8ab0\uff0c\u5982\u679c point[\u76ee\u524d\u5224\u65b7\u7684\u4f4d\u7f6e] > ans\uff0c\u5247\u4e0d\u7528\u5224\u65b7\u9019\u500b\u9ede\u76f4\u63a5 continue\u3002\u4e26\u4e14\u8981\u5728\u51fd\u5f0f\u5916\u9762\u5ba3\u544a\u4e00\u500b all_walk \u7684 Map \u4f86\u7d00\u9304\u54ea\u4e9b\u9ede\u6709\u8d70\u904e\u4e86\uff0c\u6bcf\u4e00\u6b21\u9032\u5230\u8ff4\u5708\u90fd\u8981\u5c07 all_walk[\u76ee\u524d\u4f4d\u7f6e]++\u3002<\/p>\n\n\n\n

\u5728 BFS \u4e2d\u8dd1\u5230\u7684\u9ede\u90fd\u6703\u6709\u5176\u4e0b\u4e00\u500b\u53ef\u4ee5\u8d70\u5230\u7684\u9ede\uff0c\u5ba3\u544a\u4e00\u500b newValue \u8b8a\u6578 = max(point[\u76ee\u524d BFS \u4f4d\u7f6e], \u4e0b\u4e00\u500b\u9ede\u7684 W)\u3002\u5982\u679c all_walk \u4e2d\u7d00\u9304\u9019\u500b\u9ede\u6c92\u6709\u88ab\u8d70\u904e\uff0c\u6216\u662f newValue < point[\u4e0b\u4e00\u500b\u9ede]\uff0c\u5c31\u5c07 all_walk[\u4e0b\u4e00\u500b\u9ede]++\u3001\u5c07 point[\u4e0b\u4e00\u500b\u9ede] \u66f4\u65b0\u6210 newValue\u3001\u4e26\u4e14\u5c07\u4e0b\u4e00\u500b\u9ede Push_Back \u5230\u4e0b\u4e00\u6b21\u7684 BFS \u8d77\u9ede\u4e2d\u3002<\/p>\n\n\n\n

\u5982\u679c\u904e\u7a0b\u4e2d\u8dd1\u5230\u4e86 B \u9019\u500b\u7d42\u9ede\uff0c\u5247\u5c07 ans = min(ans, point[\u76ee\u524d\u4f4d\u7f6e])\uff0c\u4e26\u4e14\u8981\u5ba3\u544a\u4e00\u500b\u5168\u57df\u5e03\u6797\u503c\u4f86\u78ba\u8a8d\u662f\u5426\u771f\u7684\u6709\u8d70\u5230\u7d42\u9ede\u904e\u3002<\/p>\n\n\n\n

\u7bc4\u4f8b\u7a0b\u5f0f\u78bc\uff0dZeroJudge E810: \u6f5b\u6c34<\/a><\/h3>\n\n\n\n
#include <iostream>\n#include <vector>\n#include <map>\nusing namespace std;\n\npair<int, int> p (const int a, const int b) {\n    pair<int, int>tmp;\n    tmp.first = a;\n    tmp.second = b;\n    return tmp;\n}\n\nint A, B, ans = 99999999, point[1000] = {};\nmap<int, vector<pair<int, int>>>road;\nmap<int, int>all_walk;\nbool ok = false;\n\nvoid BFS(const vector<int>start) {\n    if (start.size() == 0) return;\n    vector<int>newStart;\n    for (int i = 0; i<start.size(); i++) {\n        const int position = start[i];\n        const int oxygen = point[position];\n        if (oxygen > ans) continue;\n        if (position == B) {\n            ok = true;\n            ans = min(ans, oxygen);\n        }\n        all_walk[position]++;\n        const vector<pair<int, int>> begin = road[position];\n        for (int j = 0; j<begin.size(); j++) {\n            const int current = begin[j].first;\n            const int newValue = max(begin[j].second, oxygen);\n            if (all_walk[current] == 0 || newValue < point[current]) {\n                all_walk[current]++;\n                point[current] = newValue;\n                newStart.push_back(current);\n            }\n        }\n    }\n    BFS(newStart);\n}\n\nint main() {\n    cin.sync_with_stdio(0);\n    cin.tie(0);\n    int N, M;\n    cin >> N >> M;\n    for (int i = 0; i<N; i++) point[i] = 99999999;\n    for (int i = 0; i<M; i++) {\n        int a, b, W;\n        cin >> a >> b >> W;\n        road[a].push_back(p(b, W));\n        road[b].push_back(p(a, W));\n    }\n    cin >> A >> B;\n    vector<int>start;\n    start.push_back(A);\n    point[A] = 0;\n    BFS(start);\n    if (ok) cout << ans << "\\n";\n    else cout << "-1\\n";\n}\n\n\/\/ZeroJudge E810\n\/\/Dr. SeanXD<\/code><\/pre><\/div>\n","protected":false},"excerpt":{"rendered":"
\u5c0f\u8ed2\u662f\u4e00\u500b\u71b1\u611b\u6f5b\u6c34\u7684\u4eba\uff0c\u4ed6\u8d81\u8457\u653e\u6691\u5047\u7684\u6642\u9593\u53bb\u6f8e\u6e56\u6f5b\u6c34\u3002\u6f8e\u6e56\u7531\u8a31\u591a\u5c0f\u5cf6\u7d44\u6210\uff0c\u5c0f\u8ed2\u4eca\u5929\u60f3\u5f9e A \u5cf6\u7d93\u7531\u6f5b\u6c34\u7684\u65b9\u5f0f\u5230 […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"nf_dc_page":"","footnotes":""},"categories":[25],"tags":[30,14,23,20,8,34,9],"class_list":["post-1125","post","type-post","status-publish","format-standard","hentry","category-ioi-apcs","tag-bfs","tag-map","tag-pair","tag-20","tag-8","tag-34","tag-9"],"blocksy_meta":[],"_links":{"self":[{"href":"https:\/\/seanxd.com\/zh\/wp-json\/wp\/v2\/posts\/1125","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/seanxd.com\/zh\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/seanxd.com\/zh\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/seanxd.com\/zh\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/seanxd.com\/zh\/wp-json\/wp\/v2\/comments?post=1125"}],"version-history":[{"count":5,"href":"https:\/\/seanxd.com\/zh\/wp-json\/wp\/v2\/posts\/1125\/revisions"}],"predecessor-version":[{"id":1130,"href":"https:\/\/seanxd.com\/zh\/wp-json\/wp\/v2\/posts\/1125\/revisions\/1130"}],"wp:attachment":[{"href":"https:\/\/seanxd.com\/zh\/wp-json\/wp\/v2\/media?parent=1125"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/seanxd.com\/zh\/wp-json\/wp\/v2\/categories?post=1125"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/seanxd.com\/zh\/wp-json\/wp\/v2\/tags?post=1125"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}