{"id":119,"date":"2023-05-12T10:41:19","date_gmt":"2023-05-12T02:41:19","guid":{"rendered":"https:\/\/forelink.top\/?p=119"},"modified":"2023-05-12T10:44:38","modified_gmt":"2023-05-12T02:44:38","slug":"%e5%9b%be%e8%ae%ba%ef%bc%88week-9%ef%bc%89","status":"publish","type":"post","link":"https:\/\/forelink.top\/index.php\/2023\/05\/12\/%e5%9b%be%e8%ae%ba%ef%bc%88week-9%ef%bc%89\/","title":{"rendered":"\u56fe\u8bba\uff08week 9\uff09"},"content":{"rendered":"\n

T1 \u67e5\u627e\u6587\u732e (dfs bfs\u6a21\u677f\u9898\uff09<\/strong><\/h2>\n\n\n\n
\"\"<\/div><\/figure>\n\n\n\n

\u4e0b\u9644\u4ee3\u7801\uff1a<\/strong><\/p>\n\n\n\n

#include <bits\/stdc++.h>\nusing namespace std;\nconst int maxx=1e6+5;\nint n,m;\nint vis[maxx];\nvector<int> book[maxx];\nqueue<int> b;\nvoid dfs(int x){\n\tif(vis[x]==1) return;\n\tvis[x]=1;\n\tcout<<x<<' ';\n\tfor(int i=0;i<book[x].size();++i){\n\t\tdfs(book[x][i]);\n\t}\n}\nvoid bfs(){\n\tb.push(1);\n\twhile(!b.empty()){\n\t\tint x=b.front();\n\t\tb.pop();\n\t\tcout<<x<<' ';\n\t\tvis[x]=1;\n\t\tfor(int i=0;i<book[x].size();++i){\n\t\t\tint next=book[x][i];\n\t\t\tif(vis[next]==1) continue;\n\t\t\telse{\n\t\t\t\tb.push(next);\n\t\t\t\tvis[next]=1;\n\t\t\t}\n\t\t}\n\t}\n}\nint main(){\n\tcin>>n>>m;\n\tfor(int i=1;i<=m;i++){\n\t\tint f,e;\n\t\tcin>>f>>e;\n\t\tbook[f].push_back(e);\n\t}\n\tfor(int i=1;i<=n;i++){\n\t\tsort(book[i].begin(),book[i].end());\n\t}\/\/\u6392\u5e8fn\u79cd\u8d44\u6599\n\tdfs(1);\n\tcout<<endl;\n\tmemset(vis,0,sizeof(vis));\n\tbfs();\n\treturn 0;\n}<\/code><\/pre>\n\n\n\n
\n\n\n\n
T2 Floyd\uff08\u6700\u77ed\u8defn^3\u6a21\u677f\u9898\uff09<\/h2>\n\n\n\n
\"\"<\/div><\/figure>\n\n\n\n
floyd\u6bd4\u8f83\u77ed\uff0c\u672c\u8d28\u4e0a\u662f\u4e00\u79cddp\u7b97\u6cd5\u3002\u65f6\u95f4\u590d\u6742\u5ea6\u4e3a n^3\uff0cn<10^3\u5185\u7684\u6570\u636e\u53ef\u4ee5\u7528\u3002floyd\u9002\u7528\u6027\u4e5f\u5f88\u9ad8\uff0c\u904d\u5386\u6240\u6709\u70b9\u6240\u4ee5\u53ef\u4ee5\u505a\u5230\u4e00\u4e9b\u751f\u6210\u6811\u7b97\u6cd5\u7684\u529f\u80fd\u3002<\/strong><\/p>\n\n\n\n
\u4e0b\u9644\u4ee3\u7801\uff1a<\/strong><\/p>\n\n\n\n
#include <iostream>\n#include <cstring>\nusing namespace std;\nconst long long int mod = 998244354;\nconst long long int INF=25e13+500;\nint n,m;\nlong long int ans;\nlong long int map[505][505];\nint main(){\n\tfor(int i=1;i<=503;i++)\n\tfor(int l=1;l<=503;l++){\n\t\tif(i==l) map[i][l]=0;\n\t\telse map[i][l]=INF;\n\t}\n\tcin>>n>>m;\n\tfor(int i=1;i<=m;i++){\n\t\tint s,e,v;\n\t\tcin>>s>>e>>v;\n\t\tif(map[s][e]!=0&&map[s][e]>v){\n\t\t\tmap[s][e]=v;\n\t\t\tmap[e][s]=v;\n\t\t}\n\t\t\/\/\u65e0\u5411\u56fe\u3002\n\t}\n\tfor(int k=1;k<=n;k++){\n\t\tfor(int i=1;i<=n;i++){\n\t\t\tfor(int l=1;l<=n;l++){\n\t\t\t\tif(i==l) continue;\n\t\t\t\tif(map[k][l]<INF&&map[i][k]<INF&&map[i][l]>(map[k][l]+map[i][k]))\n\t\t\t\tmap[i][l]=(map[k][l]+map[i][k]);\n\t\t\t}\n\t\t}\n\t}\n\tfor(int i=1;i<=n;i++){\n\t\tans=0;\n\t\tfor(int l=1;l<=n;l++){\n\t\t\tans+=map[i][l];\n\t\t\tans%=mod;\n\t\t}\n\t\tcout<<ans%mod<<endl;\n\t}\n\treturn 0;\n}<\/code><\/pre>\n\n\n\n
\n\n\n\n
T3 \u5355\u6e90\u6700\u77ed\u8def\u5f84\uff08\u6807\u51c6\u7248\uff09<\/h2>\n\n\n\n
\u7528dijkstra\u65f6\u8981\u7528\u5806\u6765\u4f18\u5316\u7f29\u8fb9\u8fc7\u7a0b\u7684\u9009\u70b9\u6b65\u9aa4\uff0c\u53ef\u4ee5\u7528\u4f18\u5148\u961f\u5217\u6765\u5b58\u653e\u5230\u5404\u70b9\u7684\u4f30\u8ba1\u503c\u3002<\/strong><\/p>\n\n\n\n
\"\"<\/div><\/figure>\n\n\n\n
\u5404\u79cd\u5b58\u56fe\u65b9\u5f0f\uff0c\u4ee3\u7801\u7528\u4e86vector\u6570\u7ec4\u8fdb\u884c\u5b58\u56fe<\/strong><\/p>\n\n\n\n
\"\"<\/div><\/figure>\n\n\n\n
\u4e0b\u9644\u4ee3\u7801\uff1a<\/strong><\/p>\n\n\n\n
#include <iostream>\n#include <queue>\n#include <vector>\nusing namespace std;\nconst int inf=2e9+5;\nstruct point{\n\tint end,len;\n\tbool operator < (const point a) const{\n\t\treturn len < a.len;\n\t}\/\/\u91cd\u8f7d\u8fd0\u7b97\u7b26\n\tbool operator > (const point a) const{\n\t\treturn len > a.len;\n\t}\n};\nint n,m,st,cnt,now;\nbool book[100005];\nvector <point> a[100005];\/\/\u6700\u591a1e5\u4e2a\u70b9\npriority_queue <point, vector<point>,greater<point> > dis;\nint ans[100005];\/\/\u5b58\u7b54\u6848\u7684\u6570\u7ec4\u3002\nint main(){\n\tcin>>n>>m>>st;\n\tfor(int i=1;i<=100005;i++){\n\t\tans[i]=inf;\n\t}\n\tans[st]=0;\n\tfor(int i=1;i<=m;i++){\n\t\tint s,e,v;\n\t\tcin>>s>>e>>v;\n\t\ta[s].push_back({e,v});\n\t}\/\/vector\u5b58\u56fe\n\tdis.push({st,0});\/\/\u5b58\u5165\u8d77\u70b9\n\twhile(!dis.empty()){\n\t\tpoint temp=dis.top();\n\t\tdis.pop();\n\t\tnow=temp.end;\n\t\t\/\/\u56e0\u4e3a\u786e\u5b9a\u503c\u4e0d\u80fd\u91cd\u590d\u66f4\u65b0\uff08\u4f18\u5148\u961f\u5217\u5185\u4ecd\u53ef\u80fd\u5b58\u5728\n\t\t\/\/\u6240\u4ee5\u8981\u52a0\u4e00\u4e2a\u5224\u65ad\u3002\n\t\tif(!book[now]){\n\t\t\tbook[now]=true;\n\t\t\tfor(int i=0;i<a[now].size();i++){\n\t\t\t\t\/\/\u904d\u5386\u6240\u6709\u8fb9 vector\u4e0b\u6807\u4ece0\u5f00\u59cb\n\t\t\t\tpoint x=a[now][i];\n\t\t\t\tint to=x.end;\n\t\t\t\tint v=x.len;\n\t\t\t\t\/\/dijkstra\u6838\u5fc3\u4ee3\u7801\n\t\t\t\tif(ans[to]>ans[now]+v){\n\t\t\t\t\tans[to]=ans[now]+v;\n\t\t\t\t\/\/dijkstra\u6838\u5fc3\u4ee3\u7801\n\t\t\t\t\tif(!book[to]){\n\t\t\t\t\t\t\/\/\u51cf\u5c11\u5224\u65ad\u6b21\u6570\uff0c\u53bb\u6389\u4e0d\u5f71\u54cd\u7b97\u6cd5\u6b63\u786e\u6027\u3002\n\t\t\t\t\t\tdis.push({to,ans[to]});\n\t\t\t\t\t}\n\t\t\t\t}\n\t\t\t}\n\t\t}\n\t}\n\tfor(int i=1;i<=n;i++){\n\t\tcout<<ans[i]<<' ';\n\t}\n\treturn 0;\n}<\/code><\/pre>\n\n\n\n
\n","protected":false},"excerpt":{"rendered":"
T1 \u67e5\u627e\u6587\u732e (dfs bfs\u6a21\u677f\u9898\uff09 \u4e0b\u9644\u4ee3\u7801\uff1a T2 Floyd\uff08\u6700\u77ed\u8defn^3\u6a21\u677f\u9898\uff09 floyd\u6bd4\u8f83\u77ed […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_import_markdown_pro_load_document_selector":0,"_import_markdown_pro_submit_text_textarea":"","footnotes":""},"categories":[3,14,1],"tags":[],"class_list":["post-119","post","type-post","status-publish","format-standard","hentry","category-3","category-14","category-uncategorized"],"_links":{"self":[{"href":"https:\/\/forelink.top\/index.php\/wp-json\/wp\/v2\/posts\/119","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/forelink.top\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/forelink.top\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/forelink.top\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/forelink.top\/index.php\/wp-json\/wp\/v2\/comments?post=119"}],"version-history":[{"count":5,"href":"https:\/\/forelink.top\/index.php\/wp-json\/wp\/v2\/posts\/119\/revisions"}],"predecessor-version":[{"id":128,"href":"https:\/\/forelink.top\/index.php\/wp-json\/wp\/v2\/posts\/119\/revisions\/128"}],"wp:attachment":[{"href":"https:\/\/forelink.top\/index.php\/wp-json\/wp\/v2\/media?parent=119"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/forelink.top\/index.php\/wp-json\/wp\/v2\/categories?post=119"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/forelink.top\/index.php\/wp-json\/wp\/v2\/tags?post=119"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}