\u6709\u4e00\u5f20\u56fe\uff0c\u627e\u4e00\u4e2a\u70b9\u51fa\u53d1\uff0c\u4f7f\u5f97\u5230\u8fbe\u6700\u8fdc\u7684\u70b9\u4ee3\u4ef7\u6700\u5c0f\uff0c\u8f93\u51fak\u5230\u4e2a\u70b9\u7684\u6700\u5c0f\u4ee3\u4ef7\u548c\u6700\u5927\u4ef7\u503c<\/p>\n
\u5148\u7528floyd\u8dd1\u4e00\u904d\u7b97\u51fa\u6700\u8fdc\u7aef\u70b9\u4ee3\u4ef7\u6700\u5c0f\u7684\u70b9\u3002\u7136\u540e\u518d\u7528dijkstra\u7b97\u51fa\u5230k\u4e2a\u70b9\u7684\u6700\u5c0f\u4ee3\u4ef7\u548c\u6700\u5927\u4ef7\u503c<\/p>\n
\u4ee3\u7801<\/h4>\n#include <algorithm>\n#include <bitset>\n#include <cmath>\n#include <cstdio>\n#include <cstdlib>\n#include <cstring>\n#include <fstream>\n#include <functional>\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\n#define x first\n#define y second\n#define int long long\n#define endl '\\n'\n#define IOS \\\n ios_base::sync_with_stdio(0); \\\n cin.tie(0); \\\n cout.tie(0);\n\nusing namespace std;\n\ntypedef long long ll;\ntypedef pair<ll, ll> pll;\ntypedef pair<int, int> pii;\ntypedef unsigned long long ull;\n\nconst int INF = 0x3f3f3f3f, mod = 1000000007;\nconst int N = 2100;\nstruct edge {\n int to, v, w;\n};\nstruct node {\n int x, v, w;\n bool operator<(const node& w) const\n {\n if (v == w.v)\n return this->w < w.w;\n return v > w.v;\n }\n};\nvector<edge> a[N];\nint dist[N], val[N], vis[N], d[N][N];\nint n, m, st;\n\nvoid floyd()\n{\n for (int k = 1; k <= n; k++) {\n for (int i = 1; i <= n; i++) {\n for (int j = 1; j <= n; j++) {\n d[i][j] = min(d[i][j], d[i][k] + d[k][j]);\n }\n }\n }\n int sum = INF;\n for (int i = 1; i <= n; i++) {\n int res = 0;\n for (int j = 1; j <= n; j++) {\n \/\/ if (d[i][j] != INF) {\n res = max(res, d[i][j]);\n \/\/ }\n }\n if (res < sum) {\n sum = res;\n st = i;\n }\n }\n}\n\nint fa[N];\nvoid dfs(int u)\n{\n if (fa[u] == -1) {\n return;\n }\n dfs(fa[u]);\n cout << "->" << u;\n}\n\nvoid dijkstra(int u)\n{\n for (int i = 1; i <= n; i++) {\n fa[i] = -1;\n dist[i] = INF;\n }\n\n dist[u] = 0, val[u] = 0;\n priority_queue<node> q;\n q.push({ u, 0, 0 });\n while (q.size()) {\n auto t = q.top();\n q.pop();\n int u = t.x;\n if (vis[u])\n continue;\n vis[u] = 1;\n for (auto i : a[u]) {\n int v = i.to;\n if (dist[v] > dist[u] + i.v) {\n fa[v] = u;\n dist[v] = dist[u] + i.v;\n val[v] = val[u] + i.w;\n q.push({ v, dist[v], val[v] });\n } else if (dist[v] == dist[u] + i.v && val[v] < val[u] + i.w) {\n fa[v] = u;\n val[v] = val[u] + i.w;\n q.push({v, dist[v], val[v] });\n }\n }\n }\n}\n\nvoid solve()\n{\n memset(d, 0x3f, sizeof d);\n cin >> n >> m;\n\n for (int i = 1; i <= m; i++) {\n int x, y, w1, w2;\n cin >> x >> y >> w1 >> w2;\n d[x][x] = d[y][y] = 0;\n d[x][y] = d[y][x] = w1;\n a[x].push_back({ y, w1, w2 });\n a[y].push_back({ x, w1, w2 });\n }\n floyd();\n \/\/ cout << "st" << st << endl;\n dijkstra(st);\n int k;\n cin >> k;\n cout << st << endl;\n for (int i = 0; i < k; i++) {\n int x;\n cin >> x;\n cout << st;\n dfs(x);\n cout << endl;\n cout << dist[x] << " " << val[x] << endl;\n }\n}\nsigned main()\n{\n \/\/ IOS;\n int _ = 1;\n \/\/ cin >> _;\n while (_--) {\n solve();\n }\n return 0;\n}<\/code><\/pre>\n\u9898\u89e32<\/h3>\n
\u76f4\u63a5\u4e24\u904dfloyd,\u8fd9\u8fb9\u9700\u8981\u5b66\u4e60floyd\u600e\u4e48\u5b58\u56fe<\/p>\n
#include <algorithm>\n#include <bitset>\n#include <cmath>\n#include <cstdio>\n#include <cstdlib>\n#include <cstring>\n#include <fstream>\n#include <functional>\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\n#define x first\n#define y second\n#define int long long\n#define endl '\\n'\n#define IOS \\\n ios_base::sync_with_stdio(0); \\\n cin.tie(0); \\\n cout.tie(0);\n\nusing namespace std;\n\ntypedef long long ll;\ntypedef pair<ll, ll> pll;\ntypedef pair<int, int> pii;\ntypedef unsigned long long ull;\n\nconst int INF = 0x3f3f3f3f, mod = 1000000007;\nconst int N = 2100;\n\nint path[N][N], val[N][N], d[N][N];\nint n, m, st;\nvoid floyd()\n{\n\n for (int k = 1; k <= n; k++) {\n for (int i = 1; i <= n; i++) {\n for (int j = 1; j <= n; j++) {\n if (d[i][j] > d[i][k] + d[k][j]) {\n d[i][j] = d[i][k] + d[k][j];\n val[i][j] = val[i][k] + val[k][j];\n path[i][j] = k;\n } else if (d[i][j] == d[i][k] + d[k][j] && val[i][j] < val[i][k] + val[k][j]) {\n val[i][j] = val[i][k] + val[k][j];\n path[i][j] = k;\n }\n }\n }\n }\n int sum = INF;\n for (int i = 1; i <= n; i++) {\n int res = 0;\n for (int j = 1; j <= n; j++) {\n res = max(res, d[i][j]);\n }\n if (res < sum) {\n sum = res;\n st = i;\n }\n }\n}\n\nvoid print(int i, int j)\n{\n if (i == j)\n return;\n if (path[i][j] == 0)\n cout << "->" << j;\n else {\n print(i, path[i][j]);\n print(path[i][j], j);\n }\n}\n\nvoid solve()\n{\n memset(d, 0x3f, sizeof d);\n cin >> n >> m;\n for (int i = 1; i <= m; i++) {\n int x, y, w1, w2;\n cin >> x >> y >> w1 >> w2;\n d[x][x] = d[y][y] = 0;\n d[x][y] = d[y][x] = w1;\n val[x][x] = val[y][y] = 0;\n val[x][y] = val[y][x] = w2;\n }\n floyd();\n int k;\n cin >> k;\n cout << st << endl;\n for (int i = 0; i < k; i++) {\n int x;\n cin >> x;\n cout << st;\n print(st, x);\n cout << endl;\n cout << d[x][st] << " " << val[x][st] << endl;\n }\n}\nsigned main()\n{\n \/\/ IOS;\n int _ = 1;\n \/\/ cin >> _;\n while (_--) {\n solve();\n }\n return 0;\n}<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"\u9898\u76ee\u94fe\u63a5 \u94fe\u63a5 \u9898\u76ee\u5927\u610f \u6709\u4e00\u5f20\u56fe\uff0c\u627e\u4e00\u4e2a\u70b9\u51fa\u53d1\uff0c\u4f7f\u5f97\u5230\u8fbe\u6700\u8fdc\u7684\u70b9\u4ee3\u4ef7\u6700\u5c0f\uff0c\u8f93\u51fak\u5230\u4e2a\u70b9\u7684\u6700\u5c0f\u4ee3\u4ef7\u548c\u6700\u5927\u4ef7\u503c \u9898\u89e3 \u9898\u89e31 \u5148\u7528floyd\u8dd1\u4e00\u904d\u7b97\u51fa\u6700\u8fdc\u7aef\u70b9\u4ee3\u4ef7\u6700\u5c0f\u7684\u70b9\u3002\u7136\u540e\u518d\u7528dijkstra\u7b97\u51fa\u5230k\u4e2a\u70b9\u7684\u6700\u5c0f\u4ee3\u4ef7\u548c\u6700\u5927\u4ef7\u503c \u4ee3\u7801 #include <algorithm> #include <bitset> #include <cmath> #include <cstdio> #include <cstdlib> #include <cstring> #include <fstream> #include <functional> #include <iostream> #include <map> #include <queue> #include <set> #include <stack> #include <unordered_map> #include <unordered_set> #include <vector> #define x first #define y second #define int long long #define endl '\\n' #define IOS […]<\/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":[26,58,27],"class_list":["post-253","post","type-post","status-publish","format-standard","hentry","category-solution","tag-dijkstra","tag-floyd","tag-27"],"_links":{"self":[{"href":"https:\/\/solost.cn\/index.php?rest_route=\/wp\/v2\/posts\/253","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=253"}],"version-history":[{"count":0,"href":"https:\/\/solost.cn\/index.php?rest_route=\/wp\/v2\/posts\/253\/revisions"}],"wp:attachment":[{"href":"https:\/\/solost.cn\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=253"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/solost.cn\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=253"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/solost.cn\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=253"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}