{"id":116,"date":"2023-03-31T22:13:00","date_gmt":"2023-03-31T14:13:00","guid":{"rendered":"https:\/\/solost.cn\/?p=116"},"modified":"2023-03-31T22:14:00","modified_gmt":"2023-03-31T14:14:00","slug":"221","status":"publish","type":"post","link":"https:\/\/solost.cn\/?p=116","title":{"rendered":"AcWing – 1488. \u6700\u77ed\u8ddd\u79bb"},"content":{"rendered":"

\"image(1).png\"<\/p>\n

\u9898\u76ee\u94fe\u63a5<\/h2>\n

\u94fe\u63a5<\/a><\/p>\n

\u9898\u76ee\u5927\u610f<\/h2>\n

\u8fd9\u9053\u9898\u95ee\u4f60\uff0c\u7ed9\u4f60n\u4e2a\u6751\u5e84\uff0c\u6709\u4e9b\u6751\u5e84\u6709\u5546\u5e97\uff0c\u6709\u4e9b\u6751\u5e84\u6ca1\u5546\u5e97\uff0c\u95ee\u4f60\u4ece\u67d0\u4e2a\u6751\u5e84\u51fa\u53d1\uff0c\u627e\u5230\u4e00\u4e2a\u5546\u5e97\u6700\u77ed\u8ddd\u79bb\u662f\u591a\u5c11\u3002<\/p>\n

\u9898\u89e3<\/h2>\n

\u8fd9\u9898\u4e00\u773c\u9876\u9488\u3002\u6ca1\u770b\u51fa\u6765\uff0c\u672c\u6765\u60f3\u7684\u662f\u4ece\u8be2\u95ee\u7684\u70b9\u5f00\u59cb\u6bcf\u6b21spfa\u4e00\u6b21\uff0c\u4f46\u662f\uff0c\u4f46\u662f\uff0c\u80af\u5b9a\u4f1a\u8d85\u65f6\u7684\u5566\u3002\u7136\u540e\u5c31\u6709\u4e00\u4e2a\u5f88\u9a9a\u7684\u64cd\u4f5c\uff0c\u628a\u8fd9\u4e9b\u6709\u5546\u5e97\u7684\u6751\u5e84\u76f4\u63a5\u8bbe\u7f6e\u62100\uff0c\u7136\u540e\u95ee\u9898\u5c31\u8f6c\u5316\u6210<\/p>\n

\u4ece\u6709\u5546\u5e97\u7684\u6751\u5e84\u5230\u90a3\u4e9b\u6ca1\u5546\u5e97\u7684\u6751\u5e84\u7684\u6700\u77ed\u8ddd\u79bb\uff0c\u8fd9\u5c31\u5f88\u9a9a\u4e86<\/p><\/blockquote>\n

\u7136\u540e\u73b0\u573a\u518d\u8bf4\u4e00\u4e0bspfa\u7684\u63a8\u5bfc<\/p>\n

\u5f53\u524d\u70b9ver,\u4e0b\u4e00\u4e2a\u70b9\u4e3ax\uff0c\u5230\u4e0b\u4e00\u4e2a\u70b9\u7684\u8ddd\u79bb\u662fy\uff0c\u90a3\u4e48dist[x] = min(dist[x], dist[ver] + y)<\/code><\/p>\n

\u5c31\u662f\u8fd9\u6837\uff0c\u4e0a\u4ee3\u7801<\/p>\n

#include <algorithm>\n#include <bitset>\n#include <cmath>\n#include <cstdio>\n#include <cstdlib>\n#include <cstring>\n#include <fstream>\n#include <iostream>\n#include <map>\n#include <queue>\n#include <set>\n#include <stack>\n#include <unordered_map>\n#include <unordered_set>\n#include <vector>\n\nusing namespace std;\n#define x first\n#define y second\n#define endl '\\n'\n#define IOS                       \\\n    ios_base::sync_with_stdio(0); \\\n    cin.tie(0);                   \\\n    cout.tie(0);\ntypedef long long ll;\ntypedef pair<ll, ll> PLL;\ntypedef pair<int, int> PII;\n\nconst int INF = 0x3f3f3f3f, mod = 1000000007;\nconst int N = 2e5 + 10;\nint n, m;\nvector<PII> g[N];\nmap<int, int> v;\nint dist[N];\nint res;\nvoid spfa()\n{\n    res = INF;\n    memset(dist, 0x3f, sizeof dist);\n    queue<int> q;\n    q.push(0);\n    dist[0] = 0;\n    while (q.size()) {\n        auto t = q.front();\n        q.pop();\n        for (auto [x, y] : g[t]) {\n            if (dist[x] > dist[t] + y) {\n                dist[x] = dist[t] + y;\n                q.push(x);\n            }\n            if (v[x]) {\n                res = min(res, dist[x]);\n            }\n        }\n    }\n}\n\nvoid solve()\n{\n    cin >> n >> m;\n    for (int i = 1; i <= m; i++) {\n        int a, b, c;\n        cin >> a >> b >> c;\n        g[a].push_back({ b, c });\n        g[b].push_back({ a, c });\n    }\n    int k;\n    cin >> k;\n    while (k--) {\n        int x;\n        cin >> x;\n        g[0].push_back({ x, 0 });\n        g[x].push_back({ 0, 0 });\n    }\n    int q;\n    cin >> q;\n    spfa();\n    while (q--) {\n        int x;\n        cin >> x;\n        cout << dist[x] << endl;\n    }\n}\nint main()\n{\n    \/\/ IOS;\n    int t = 1;\n    \/\/ cin >> t;\n    while (t--) {\n        solve();\n    }\n    return 0;\n}<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"
\u9898\u76ee\u94fe\u63a5 \u94fe\u63a5 \u9898\u76ee\u5927\u610f \u8fd9\u9053\u9898\u95ee\u4f60\uff0c\u7ed9\u4f60n\u4e2a\u6751\u5e84\uff0c\u6709\u4e9b\u6751\u5e84\u6709\u5546\u5e97\uff0c\u6709\u4e9b\u6751\u5e84\u6ca1\u5546\u5e97\uff0c\u95ee\u4f60\u4ece\u67d0\u4e2a\u6751\u5e84\u51fa\u53d1\uff0c\u627e\u5230\u4e00\u4e2a\u5546\u5e97\u6700\u77ed\u8ddd\u79bb\u662f\u591a\u5c11\u3002 \u9898\u89e3 \u8fd9\u9898\u4e00\u773c\u9876\u9488\u3002\u6ca1\u770b\u51fa\u6765\uff0c\u672c\u6765\u60f3\u7684\u662f\u4ece\u8be2\u95ee\u7684\u70b9\u5f00\u59cb\u6bcf\u6b21spfa\u4e00\u6b21\uff0c\u4f46\u662f\uff0c\u4f46\u662f\uff0c\u80af\u5b9a\u4f1a\u8d85\u65f6\u7684\u5566\u3002\u7136\u540e\u5c31\u6709\u4e00\u4e2a\u5f88\u9a9a\u7684\u64cd\u4f5c\uff0c\u628a\u8fd9\u4e9b\u6709\u5546\u5e97\u7684\u6751\u5e84\u76f4\u63a5\u8bbe\u7f6e\u62100\uff0c\u7136\u540e\u95ee\u9898\u5c31\u8f6c\u5316\u6210 \u4ece\u6709\u5546\u5e97\u7684\u6751\u5e84\u5230\u90a3\u4e9b\u6ca1\u5546\u5e97\u7684\u6751\u5e84\u7684\u6700\u77ed\u8ddd\u79bb\uff0c\u8fd9\u5c31\u5f88\u9a9a\u4e86 \u7136\u540e\u73b0\u573a\u518d\u8bf4\u4e00\u4e0bspfa\u7684\u63a8\u5bfc \u5f53\u524d\u70b9ver,\u4e0b\u4e00\u4e2a\u70b9\u4e3ax\uff0c\u5230\u4e0b\u4e00\u4e2a\u70b9\u7684\u8ddd\u79bb\u662fy\uff0c\u90a3\u4e48dist[x] = min(dist[x], dist[ver] + y) \u5c31\u662f\u8fd9\u6837\uff0c\u4e0a\u4ee3\u7801 #include <algorithm> #include <bitset> #include <cmath> #include <cstdio> #include <cstdlib> #include <cstring> #include <fstream> #include <iostream> #include <map> #include <queue> #include <set> #include <stack> #include <unordered_map> #include <unordered_set> #include <vector> using namespace std; #define x first #define y second #define […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[3],"tags":[25,32,8],"class_list":["post-116","post","type-post","status-publish","format-standard","hentry","category-solution","tag-bfs","tag-spfa","tag-8"],"_links":{"self":[{"href":"https:\/\/solost.cn\/index.php?rest_route=\/wp\/v2\/posts\/116","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/solost.cn\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/solost.cn\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/solost.cn\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/solost.cn\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=116"}],"version-history":[{"count":0,"href":"https:\/\/solost.cn\/index.php?rest_route=\/wp\/v2\/posts\/116\/revisions"}],"wp:attachment":[{"href":"https:\/\/solost.cn\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=116"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/solost.cn\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=116"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/solost.cn\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=116"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}