{"id":156,"date":"2024-10-15T18:26:47","date_gmt":"2024-10-15T10:26:47","guid":{"rendered":"http:\/\/8.138.167.183\/?p=156"},"modified":"2024-12-21T21:40:23","modified_gmt":"2024-12-21T13:40:23","slug":"%e6%b4%9b%e8%b0%b7-p1807-%e6%9c%80%e9%95%bf%e8%b7%af","status":"publish","type":"post","link":"https:\/\/heqiwei.cn\/index.php\/2024\/10\/15\/%e6%b4%9b%e8%b0%b7-p1807-%e6%9c%80%e9%95%bf%e8%b7%af\/","title":{"rendered":"\u6d1b\u8c37 P1807 \u6700\u957f\u8def"},"content":{"rendered":"\n
\"\"<\/div><\/figure>\n\n\n\n

\u672c\u9898\u521d\u6b21\u653e\u5f03\u4e8e2024.9.3 16:05<\/a>\uff0c\u4eca\u5929\u6d4f\u89c8\u9898\u5355\u65f6\u53d1\u73b0\u8be5\u9057\u7559\u95ee\u9898\uff0c\u51b3\u5b9a\u518d\u6b21\u6311\u6218<\/p>\n\n\n\n

\u9519\u8bef\u4ee3\u7801\uff1a<\/p>\n\n\n\n

#include<stdio.h>\n#include<stdlib.h>\n#define MIN -225555555\ntypedef struct\n{\n\tint connect, dist;\n}node;\nnode graph[1502][1502];\nint indegree[1502];\nint visit[1502];\nint visit2[1502];\nint maxdistance[1502];\nint Max(int a, int b) { return a > b ? a : b; }\nvoid dfs(int current, int p)\n{\n\tvisit2[current] = 1;\n\tfor (int i = 1; i <= p; i++)\n\t\tif (graph[current][i].connect != 0 && !visit2[i])\n\t\t\tdfs(i, p);\n}\nvoid vanish(int p, int current)\n{\n\tvisit[current] == 1;\n\tfor (int j = current + 1; j <= p; j++)\n\t\tif (graph[current][j].connect != 0 && !visit[j])\n\t\t{\n\t\t\t--indegree[j];\n\t\t\tif (indegree[j] == 0) vanish(p, j);\n\t\t}\n}\nvoid toposort(int p)\n{\n\tint queue[1502], front = 0, back = 0;\n\tqueue[front++] = 1;\n\tvisit[1] = 1;\/\/ \u5b58\u5165\u8d77\u70b91\n\tfor (int i = 2; i <= p; i++)\/\/ \u627e\u5230\u96641\u5916\u6240\u6709\u5165\u5ea6\u4e3a0\u7684\u70b9\uff0c\u5e76\u9012\u5f52\u5220\u9664\u4ed6\u4eec\u7684\u5f71\u54cd\n\t{\n\t\tif (indegree[i] == 0)\n\t\t\tvanish(p, i);\n\t}\n\twhile (front > back)\/\/ \u62d3\u6251\u6392\u5e8f\u672c\u4f53\n\t{\n\t\tint temp = queue[back++];\n\t\tvisit[temp] = 1;\n\t\tfor (int i = temp + 1; i <= p; i++)\n\t\t{\n\t\t\tif (graph[temp][i].connect != 0 && !visit[i])\n\t\t\t{\n\t\t\t\t--indegree[i];\n\t\t\t\tmaxdistance[i] = Max(maxdistance[i], maxdistance[temp] + graph[temp][i].dist);\n\t\t\t\tif (!indegree[i]) queue[front++] = i;\n\t\t\t}\n\t\t}\n\t}\n}\nint main()\n{\n\tint p, v, p1, p2, lon;\n\tscanf(\"%d%d\", &p, &v);\n\tfor (int i = 2; i <= p; i++)\n\t\tmaxdistance[i] = MIN;\n\tfor (int i = 0; i < v; i++)\n\t{\n\t\tscanf(\"%d%d%d\", &p1, &p2, &lon);\n\t\tgraph[p1][p2].connect = 1;\n\t\tgraph[p1][p2].dist = lon;\n\t\t++indegree[p2];\n\t}\n\tdfs(1, p);\n\tif (!visit2[p])\n\t{\n\t\tprintf(\"-1\");\n\t\treturn 0;\n\t}\n\ttoposort(p);\n\tprintf(\"%d\", maxdistance[p]);\n\treturn 0;\n}\n\/* \n    maybe oneday I'll be back\n                   \u2014\u2014\u2014\u20142024.9.3 16:05\n*\/<\/code><\/pre>\n\n\n\n
\u65b0\u4ee3\u7801\uff08\u8d1f\u8fb9\u90bb\u63a5\u77e9\u9635+spfa\uff09<\/a><\/p>\n\n\n\n
#include<stdio.h>\n#include<stdlib.h>\n#define MAX 0x3f3f3f3f\nint p, v, g[1502][1502], visit[1502], queue[150000], dis[1502];\nvoid spfa()\n{\n\tfor (int i = 1; i <= p; ++i) dis[i] = MAX;\n\tint front = 0, back = 0;\n\tdis[1] = 0;\n\tqueue[front++] = 1;\n\tvisit[1] = 1;\n\twhile (back < front)\n\t{\n\t\tint t = queue[back++];\n\t\tvisit[t] = 0;\n\t\tfor (int i = 1; i <= p; ++i)\n\t\t\tif (g[t][i] != MAX && dis[i] > dis[t] + g[t][i])\n\t\t\t{\n\t\t\t\tdis[i] = dis[t] + g[t][i];\n\t\t\t\tif (!visit[i])\n\t\t\t\t{\n\t\t\t\t\tqueue[front++] = i;\n\t\t\t\t\tvisit[i] = 1;\n\t\t\t\t}\n\t\t\t}\n\t}\n}\nint main()\n{\n\tint p1, p2, w;\n\tscanf(\"%d%d\", &p, &v);\n\tfor (int i = 1; i <= p; ++i)\n\t\tfor (int j = 1; j <= p; ++j)\n\t\t\tg[i][j] = MAX;\/\/ \u521d\u59cb\u5316\u90bb\u63a5\u77e9\u9635\n\tfor (int i = 0; i < v; ++i)\n\t{\n\t\tscanf(\"%d%d%d\", &p1, &p2, &w);\n\t\tg[p1][p2] = -w;\n\t}\/\/ \u8bfb\u5165\u90bb\u63a5\u77e9\u9635\uff0c\u5c06\u6743\u91cd\u53d6\u53cd\uff0c\u8f6c\u5316\u4e3aspfa\u6c42\u6700\u77ed\u8def\n\tspfa();\n\tif (dis[p] == MAX) printf(\"-1\");\n\telse printf(\"%d\", -dis[p]);\n\treturn 0;\n}<\/code><\/pre>\n\n\n\n
\u5230\u5e95\u4e3a\u4ec0\u4e48\uff0c\u90fd\u662f\u6211\u7684\u9519<\/p>\n\n\n\n
\u51b3\u5b9a\u8f6c\u7528\u94fe\u5f0f\u524d\u5411\u661f<\/p>\n\n\n\n
\u4f46\u662f\u5148\u5403\u4e2a\u996d<\/p>\n\n\n\n
\u6211\u8fd8\u662f\u51b3\u5b9a\u4e0d\u5403\u996d\u4e86<\/p>\n\n\n\n
\u2014\u2014\u2014\u2014\u2014\u2014\u2014\u2014\u2014\u2014\u2014\u2014\u2014\u2014\u2014\u2014\u2014\u2014\u2014\u2014\u2014\u2014\u2014\u2014\u2014\u2014\u2014\u2014\u2014\u2014\u2014\u2014\u2014\u2014\u2014\u2014<\/p>\n\n\n\n
\u5341\u5206\u949f\u540e\uff1a\u8fc7\u8fa3\uff01<\/a><\/p>\n\n\n\n
#include<stdio.h>\n#include<stdlib.h>\n#define MAX 0x3f3f3f3f\ntypedef struct\n{\n\tint to, next, w;\n}edge;\nedge e[50002];\nint p, v, head[1502], visit[1502], queue[150000], dis[1502], cnt = 0;\nvoid add(int p1, int p2, int w)\n{\n\te[cnt].to = p2;\n\te[cnt].w = w;\n\te[cnt].next = head[p1];\n\thead[p1] = cnt++;\n}\nvoid spfa()\n{\n\tfor (int i = 1; i <= p; ++i) dis[i] = MAX;\n\tint front = 0, back = 0;\n\tdis[1] = 0;\n\tqueue[front++] = 1;\n\tvisit[1] = 1;\n\twhile (back < front)\n\t{\n\t\tint t = queue[back++];\n\t\tvisit[t] = 0;\n\t\tfor (int i = head[t]; i != -1; i = e[i].next)\n\t\t{\n\t\t\tint to = e[i].to, w = e[i].w;\n\t\t\tif (dis[to] > dis[t] + w)\n\t\t\t{\n\t\t\t\tdis[to] = dis[t] + w;\n\t\t\t\tif (!visit[to])\n\t\t\t\t{\n\t\t\t\t\tqueue[front++] = to;\n\t\t\t\t\tvisit[to] = 1;\n\t\t\t\t}\n\t\t\t}\n\t\t}\n\t}\n}\nint main()\n{\n\tint p1, p2, w;\n\tscanf(\"%d%d\", &p, &v);\n\tfor (int i = 0; i <= p; ++i) head[i] = -1;\n\tfor (int i = 0; i < v; ++i)\n\t{\n\t\tscanf(\"%d%d%d\", &p1, &p2, &w);\n\t\tadd(p1, p2, -w);\n\t}\/\/ \u8bfb\u5165\u90bb\u63a5\u8868\uff0c\u5c06\u6743\u91cd\u53d6\u53cd\uff0c\u8f6c\u5316\u4e3aspfa\u6c42\u6700\u77ed\u8def\n\tspfa();\n\tif (dis[p] == MAX) printf(\"-1\");\n\telse printf(\"%d\", -dis[p]);\n\treturn 0;\n}<\/code><\/pre>\n\n\n\n
\u6211\u7231\u94fe\u5f0f\u524d\u5411\u661f<\/p>\n\n\n\n
\"\"<\/div><\/figure>\n\n\n\n
\u84df\u53bf\u3002<\/p>\n","protected":false},"excerpt":{"rendered":"
\u672c\u9898\u521d\u6b21\u653e\u5f03\u4e8e2024.9.3 16:05\uff0c\u4eca\u5929\u6d4f\u89c8\u9898\u5355\u65f6\u53d1\u73b0\u8be5\u9057\u7559\u95ee\u9898\uff0c\u51b3\u5b9a\u518d\u6b21\u6311\u6218 \u9519\u8bef\u4ee3\u7801\uff1a \u65b0\u4ee3\u7801\uff08\u8d1f […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1],"tags":[],"class_list":["post-156","post","type-post","status-publish","format-standard","hentry","category-1"],"_links":{"self":[{"href":"https:\/\/heqiwei.cn\/index.php\/wp-json\/wp\/v2\/posts\/156","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/heqiwei.cn\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/heqiwei.cn\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/heqiwei.cn\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/heqiwei.cn\/index.php\/wp-json\/wp\/v2\/comments?post=156"}],"version-history":[{"count":1,"href":"https:\/\/heqiwei.cn\/index.php\/wp-json\/wp\/v2\/posts\/156\/revisions"}],"predecessor-version":[{"id":823,"href":"https:\/\/heqiwei.cn\/index.php\/wp-json\/wp\/v2\/posts\/156\/revisions\/823"}],"wp:attachment":[{"href":"https:\/\/heqiwei.cn\/index.php\/wp-json\/wp\/v2\/media?parent=156"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/heqiwei.cn\/index.php\/wp-json\/wp\/v2\/categories?post=156"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/heqiwei.cn\/index.php\/wp-json\/wp\/v2\/tags?post=156"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}