\u94fe\u63a5<\/a><\/p>\nsolution<\/h2>\n
\u8fd9\u9053\u9898\u4e5f\u6ca1\u5565\u96be\u70b9\uff0c\u7eaf\u5c5e\u8111\u6b8b\u3002\u5c31\u662fBFS\u641c\u7d22\u5c31\u884c\u4e86\u3002\u6ce8\u610f\u641c\u7d22\u7684\u65f6\u5019\u7ef4\u62a4\u4e00\u4e0b\u72b6\u6001\u5c31\u884c\u3002<\/p>\n
#include<map>\n#include<set>\n#include<stack>\n#include<queue>\n#include<cmath>\n#include<vector>\n#include<bitset>\n#include<cstdio>\n#include<cstring>\n#include<fstream>\n#include<cstdlib>\n#include<iostream>\n#include<algorithm>\n#include<unordered_map>\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<int,int> PII;\ntypedef unsigned long long ull;\nconst int INF = 0x3f3f3f3f, mod = 1000000007;\nconst int N = 2e5 + 10;\nvector<PII> g[N];\nint dist[N], cnt[N];\nvoid spfa(){\n queue<PII> q;\n memset(dist, 0x3f, sizeof dist);\n memset(cnt, 0x3f, sizeof cnt);\n dist[1] = 0;\n cnt[1] = 1;\n q.push({1, 0});\n while(q.size()){\n auto t = q.front();\n q.pop();\n for(auto [x, y] : g[t.x]){\n if(cnt[x] >= cnt[t.x] + 1){\n cnt[x] = cnt[t.x] + 1;\n if(dist[x] > dist[t.x] + y){\n dist[x] = dist[t.x] + y;\n q.push({x, dist[x]});\n }\n }\n }\n }\n}\n\nvoid solve(){\n int n, m;\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 spfa();\n cout << cnt[n] << " " << dist[n] << endl;\n}\nint main(){\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 solution \u8fd9\u9053\u9898\u4e5f\u6ca1\u5565\u96be\u70b9\uff0c\u7eaf\u5c5e\u8111\u6b8b\u3002\u5c31\u662fBFS\u641c\u7d22\u5c31\u884c\u4e86\u3002\u6ce8\u610f\u641c\u7d22\u7684\u65f6\u5019\u7ef4\u62a4\u4e00\u4e0b\u72b6\u6001\u5c31\u884c\u3002 #include<map> #include<set> #include<stack> #include<queue> #include<cmath> #include<vector> #include<bitset> #include<cstdio> #include<cstring> #include<fstream> #include<cstdlib> #include<iostream> #include<algorithm> #include<unordered_map> using namespace std; #define x first #define y second #define endl '\\n' #define IOS \\ ios_base::sync_with_stdio(0); \\ cin.tie(0); \\ cout.tie(0); typedef long long ll; typedef pair<int,int> PII; typedef unsigned long long ull; const int INF = 0x3f3f3f3f, […]<\/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":[32,31,27],"class_list":["post-72","post","type-post","status-publish","format-standard","hentry","category-solution","tag-spfa","tag-31","tag-27"],"_links":{"self":[{"href":"https:\/\/solost.cn\/index.php?rest_route=\/wp\/v2\/posts\/72","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=72"}],"version-history":[{"count":0,"href":"https:\/\/solost.cn\/index.php?rest_route=\/wp\/v2\/posts\/72\/revisions"}],"wp:attachment":[{"href":"https:\/\/solost.cn\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=72"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/solost.cn\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=72"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/solost.cn\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=72"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}
![\"image.png\"](\"\/wp-content\/uploads\/2026\/11\/image-7.png\" "\\"image.png\\"")
<\/p>\n