\u7b2c\u4e00\u4e2a\u65b9\u6cd5\uff1a\u5efa $k+1$ \u7684\u5206\u5c42\u56fe\u3002<\/p>\n<\/li>\n
\u7b2c\u4e8c\u4e2a\u65b9\u6cd5\uff1a\u591a\u5f00\u4e00\u7ef4\u7684\u6570\u7ec4\u8bb0\u5f55\u51b3\u7b56\u4fe1\u606f\u3002<\/p>\n<\/li>\n<\/ul>\n
\u65b9\u6cd5\u4e00<\/h3>\n\n- \n
\u5bf9\u4e8e\u540c\u4e00\u5c42\u7684\u56fe\uff0c\u6bcf\u4e00\u5c42\u90fd\u6309\u539f\u56fe\u5efa\u8fb9\u3002<\/p>\n<\/li>\n
- \n
\u5bf9\u4e8e\u76f8\u90bb\u4e24\u5c42\u7684\u56fe\uff0c\u82e5\u539f\u56fe\u4e2d\u4ece $u$ \u5230 $v$ \u6709\u4e00\u6761\u8fb9\uff0c\u90a3\u4e48\u5c31\u4ece $u$ \u5230\u4e0b\u4e00\u5c42\u5bf9\u5e94\u7684 $v$ \u8fde\u4e00\u6761\u8fb9\uff0c\u4ece $v$ \u5230\u4e0b\u4e00\u5c42\u7684 $u$ \u4e5f\u8fde\u4e00\u6761\u3002\u8fb9\u7684\u6743\u503c\u53d6\u51b3\u4e8e\u51b3\u7b56\u5185\u5bb9\u3002<\/p>\n<\/li>\n<\/ul>\n
\u8fd9\u6837\u6211\u4eec\u5c31\u901a\u8fc7\u5efa\u56fe\u6a21\u62df\u4e86 $k$ \u6b21\u51b3\u7b56\u3002<\/p>\n
\u5177\u4f53\u53ef\u53c2\u8003\u4e0b\u9762\u8fd9\u5f20\u56fe\uff08\u5f15\u7528\u81eacyhyyds\u7684\u535a\u5ba2<\/a>\uff09\u3002<\/p>\n![\"\"](\"data:image\/svg+xml;base64,PCEtLUFyZ29uTG9hZGluZy0tPgo8c3ZnIHdpZHRoPSIxIiBoZWlnaHQ9IjEiIHhtbG5zPSJodHRwOi8vd3d3LnczLm9yZy8yMDAwL3N2ZyIgc3Ryb2tlPSIjZmZmZmZmMDAiPjxnPjwvZz4KPC9zdmc+\")
<\/p>\n
\u5177\u4f53\u7684\u5efa\u8fb9\u8fc7\u7a0b\u5982\u4e0b\uff1a<\/p>\n
for(int j=0;j<=k;j++){\n \/\/\u540c\u4e00\u5c42\u5efa\u8fb9\n add_edge(u+j*n,v+j*n,w);\n add_edge(v+j*n,u+j*n,w);\n\n \/\/\u4e24\u5c42\u95f4\u5efa\u8fb9\n add_edge(u+j*n,v+(j+1)*n,0);\n add_edge(v+j*n,u+(j+1)*n,0);\n}<\/code><\/pre>\n\u65b9\u6cd5\u4e8c<\/h3>\n
\u9996\u5148\u53ef\u4ee5\u5728\u539f\u6765\u7684\u6570\u7ec4\u4e0a\u591a\u52a0\u4e00\u7ef4\u6765\u8bb0\u5f55\u51b3\u7b56\u4fe1\u606f\uff1a<\/p>\n
\n- $dis[i][j]$ \u8868\u793a\u5230\u8fbe\u70b9 $i$ \u8fdb\u884c\u4e86 $j$ \u6b21\u51b3\u7b56\u65f6\u7684\u6700\u77ed\u8def\u3002<\/li>\n
- $vis[i][j]$ \u8868\u793a\u5230\u8fbe\u70b9 $i$ \u8fdb\u884c\u4e86 $j$ \u6b21\u51b3\u7b56\u65f6\u70b9 $i$ \u662f\u5426\u8bbf\u95ee\u8fc7\u3002<\/li>\n<\/ul>\n
\u72b6\u6001\u8f6c\u79fb\uff08$w$ \u4e3a\u8fb9\u6743\uff09\uff1a<\/p>\n
\n- $dis[v][k]=min(dis[v][k],dis[u][k]+w)$<\/li>\n
- \u53ef\u4ee5\u8fdb\u884c\u51b3\u7b56\u65f6\uff1a$dis[v][k]=min(dis[v][k],dis[u][k-1]+w)$<\/li>\n<\/ul>\n
\u5728\u8fd9\u79cd\u65b9\u6cd5\u4e2d\uff0c\u6570\u7ec4\u8bb0\u5f55\u7684\u8fdb\u884c\u4e86 $j$ \u6b21\u51b3\u7b56\uff0c\u5b9e\u9645\u4e0a\u4e5f\u53ef\u4ee5\u770b\u505a\u662f\u5728\u65b9\u6cd5\u4e00\u4e2d\u7684\u56fe\u4e0a\u5230\u8fbe\u4e86\u7b2c $j$ \u5c42\uff0c\u4e24\u8005\u662f\u7b49\u4ef7\u7684\uff0c\u590d\u6742\u5ea6\u90fd\u4e3a $O(mklog(mk))$ \u3002<\/p>\n
\u4e2a\u4eba\u6bd4\u8f83\u559c\u6b22\u7b2c\u4e00\u79cd\uff0c\u6bd5\u7adf\u591a\u52a0\u51e0\u53e5\u5efa\u4e2a\u56fe\u76f4\u63a5\u5957\u6a21\u677f\u8c01\u4e0d\u559c\u6b22\u5462<\/del>\u3002<\/p>\n\u7ec3\u4e60<\/h2>\n
P4568 [JLOI2011] \u98de\u884c\u8def\u7ebf<\/a><\/p>\n\u677f\u5b50\u9898\u3002\u56e0\u4e3a\u6b21\u6570\u4e0d\u4e00\u5b9a\u8981\u7528\u5b8c\uff0c\u6240\u4ee5\u7b54\u6848\u8981\u4ece\u6bcf\u5c42\u7ec8\u70b9\u7684\u7b54\u6848\u91cc\u53d6\u6700\u5c0f\u503c\u3002<\/p>\n
P2939 [USACO09FEB]Revamping Trails G<\/a><\/p>\n\u53cc\u500d\u7ecf\u9a8c\u3002<\/p>\n
P1948 [USACO08JAN]Telephone Lines S<\/a><\/p>\n\u4e09\u500d\u7ecf\u9a8c\uff1f\u6ce8\u610f\u9898\u76ee\u4e2d\u7684\u82b1\u8d39\u662f\u8def\u5f84\u8fb9\u6743\u6700\u5927\u503c\uff0c\u8981\u6539\u4e00\u4e0b\u6700\u77ed\u8def\u6a21\u677f\u3002<\/p>\n
P4822 [BJWC2012]\u51bb\u7ed3<\/a><\/p>\n\u5c42\u4e4b\u95f4\u7684\u8fb9\u6743\u4e3a\u539f\u8fb9\u6743\u4e00\u534a\u3002<\/p>\n
P1073 [NOIP2009 \u63d0\u9ad8\u7ec4] \u6700\u4f18\u8d38\u6613<\/a><\/p>\n\u5728\u8fd9\u9053\u9898\u4e2d\u7684\u51b3\u7b56\u662f\u4e70\u5165\u6216\u5356\u51fa\u6216\u4e0d\u4e70\u3002\u53ea\u8981\u5efa\u4e09\u5c42\u5c31\u591f\u4e86\uff0c\u7b2c\u4e00\u5c42\u5230\u7b2c\u4e8c\u5c42\u4ee3\u8868\u4e70\u5165\uff0c\u8fb9\u6743\u4e3a $-w$ \uff1b\u7b2c\u4e8c\u5c42\u5230\u7b2c\u4e09\u6b21\u4ee3\u8868\u5356\u51fa\uff0c\u8fb9\u6743\u4e3a $w$ \u3002\u6bcf\u4e00\u5c42\u5185\u8fb9\u6743\u5747\u4e3a 0 \u3002<\/p>\n
\n\u672c\u7bc7\u53c2\u8003\uff1a<\/p>\n
\u5206\u5c42\u56fe\u6700\u77ed\u8def - Eleven\u8c26 - \u535a\u5ba2\u56ed<\/a><\/p>\n
\u5bf9\u4e8e\u540c\u4e00\u5c42\u7684\u56fe\uff0c\u6bcf\u4e00\u5c42\u90fd\u6309\u539f\u56fe\u5efa\u8fb9\u3002<\/p>\n<\/li>\n
\u5bf9\u4e8e\u76f8\u90bb\u4e24\u5c42\u7684\u56fe\uff0c\u82e5\u539f\u56fe\u4e2d\u4ece $u$ \u5230 $v$ \u6709\u4e00\u6761\u8fb9\uff0c\u90a3\u4e48\u5c31\u4ece $u$ \u5230\u4e0b\u4e00\u5c42\u5bf9\u5e94\u7684 $v$ \u8fde\u4e00\u6761\u8fb9\uff0c\u4ece $v$ \u5230\u4e0b\u4e00\u5c42\u7684 $u$ \u4e5f\u8fde\u4e00\u6761\u3002\u8fb9\u7684\u6743\u503c\u53d6\u51b3\u4e8e\u51b3\u7b56\u5185\u5bb9\u3002<\/p>\n<\/li>\n<\/ul>\n
\u8fd9\u6837\u6211\u4eec\u5c31\u901a\u8fc7\u5efa\u56fe\u6a21\u62df\u4e86 $k$ \u6b21\u51b3\u7b56\u3002<\/p>\n
\u5177\u4f53\u53ef\u53c2\u8003\u4e0b\u9762\u8fd9\u5f20\u56fe\uff08\u5f15\u7528\u81eacyhyyds\u7684\u535a\u5ba2<\/a>\uff09\u3002<\/p>\n \u5177\u4f53\u7684\u5efa\u8fb9\u8fc7\u7a0b\u5982\u4e0b\uff1a<\/p>\n \u9996\u5148\u53ef\u4ee5\u5728\u539f\u6765\u7684\u6570\u7ec4\u4e0a\u591a\u52a0\u4e00\u7ef4\u6765\u8bb0\u5f55\u51b3\u7b56\u4fe1\u606f\uff1a<\/p>\n \u72b6\u6001\u8f6c\u79fb\uff08$w$ \u4e3a\u8fb9\u6743\uff09\uff1a<\/p>\n \u5728\u8fd9\u79cd\u65b9\u6cd5\u4e2d\uff0c\u6570\u7ec4\u8bb0\u5f55\u7684\u8fdb\u884c\u4e86 $j$ \u6b21\u51b3\u7b56\uff0c\u5b9e\u9645\u4e0a\u4e5f\u53ef\u4ee5\u770b\u505a\u662f\u5728\u65b9\u6cd5\u4e00\u4e2d\u7684\u56fe\u4e0a\u5230\u8fbe\u4e86\u7b2c $j$ \u5c42\uff0c\u4e24\u8005\u662f\u7b49\u4ef7\u7684\uff0c\u590d\u6742\u5ea6\u90fd\u4e3a $O(mklog(mk))$ \u3002<\/p>\n \u4e2a\u4eba\u6bd4\u8f83\u559c\u6b22\u7b2c\u4e00\u79cd\uff0c P4568 [JLOI2011] \u98de\u884c\u8def\u7ebf<\/a><\/p>\n \u677f\u5b50\u9898\u3002\u56e0\u4e3a\u6b21\u6570\u4e0d\u4e00\u5b9a\u8981\u7528\u5b8c\uff0c\u6240\u4ee5\u7b54\u6848\u8981\u4ece\u6bcf\u5c42\u7ec8\u70b9\u7684\u7b54\u6848\u91cc\u53d6\u6700\u5c0f\u503c\u3002<\/p>\n P2939 [USACO09FEB]Revamping Trails G<\/a><\/p>\n \u53cc\u500d\u7ecf\u9a8c\u3002<\/p>\n P1948 [USACO08JAN]Telephone Lines S<\/a><\/p>\n \u4e09\u500d\u7ecf\u9a8c\uff1f\u6ce8\u610f\u9898\u76ee\u4e2d\u7684\u82b1\u8d39\u662f\u8def\u5f84\u8fb9\u6743\u6700\u5927\u503c\uff0c\u8981\u6539\u4e00\u4e0b\u6700\u77ed\u8def\u6a21\u677f\u3002<\/p>\n P4822 [BJWC2012]\u51bb\u7ed3<\/a><\/p>\n \u5c42\u4e4b\u95f4\u7684\u8fb9\u6743\u4e3a\u539f\u8fb9\u6743\u4e00\u534a\u3002<\/p>\n P1073 [NOIP2009 \u63d0\u9ad8\u7ec4] \u6700\u4f18\u8d38\u6613<\/a><\/p>\n \u5728\u8fd9\u9053\u9898\u4e2d\u7684\u51b3\u7b56\u662f\u4e70\u5165\u6216\u5356\u51fa\u6216\u4e0d\u4e70\u3002\u53ea\u8981\u5efa\u4e09\u5c42\u5c31\u591f\u4e86\uff0c\u7b2c\u4e00\u5c42\u5230\u7b2c\u4e8c\u5c42\u4ee3\u8868\u4e70\u5165\uff0c\u8fb9\u6743\u4e3a $-w$ \uff1b\u7b2c\u4e8c\u5c42\u5230\u7b2c\u4e09\u6b21\u4ee3\u8868\u5356\u51fa\uff0c\u8fb9\u6743\u4e3a $w$ \u3002\u6bcf\u4e00\u5c42\u5185\u8fb9\u6743\u5747\u4e3a 0 \u3002<\/p>\n \u672c\u7bc7\u53c2\u8003\uff1a<\/p>\n \u5206\u5c42\u56fe\u6700\u77ed\u8def - Eleven\u8c26 - \u535a\u5ba2\u56ed<\/a><\/p>\n![\"\"](\"https:\/\/cdn.luogu.com.cn\/upload\/image_hosting\/f0f6dz75.png\")
<\/p>\nfor(int j=0;j<=k;j++){\n \/\/\u540c\u4e00\u5c42\u5efa\u8fb9\n add_edge(u+j*n,v+j*n,w);\n add_edge(v+j*n,u+j*n,w);\n\n \/\/\u4e24\u5c42\u95f4\u5efa\u8fb9\n add_edge(u+j*n,v+(j+1)*n,0);\n add_edge(v+j*n,u+(j+1)*n,0);\n}<\/code><\/pre>\n\u65b9\u6cd5\u4e8c<\/h3>\n
\n
\n
\u6bd5\u7adf\u591a\u52a0\u51e0\u53e5\u5efa\u4e2a\u56fe\u76f4\u63a5\u5957\u6a21\u677f\u8c01\u4e0d\u559c\u6b22\u5462<\/del>\u3002<\/p>\n\u7ec3\u4e60<\/h2>\n
\n