\u9996\u5148\u770b\u5230\u70b9\u6570\uff0c\u5c31\u8003\u8651\u62c6\u70b9\u3002
\n\u628a\u6bcf\u4e00\u4e2a\u70b9\u62c6\u6210k\u4e2a\u70b9\uff0c\u5206\u522b\u8868\u793a\u5df2\u7ecf\u5403\u4e86k\u6b21\u514d\u8d39\u5348\u9910\u7684\u8ddd\u79bb\u3002
\n\u7136\u540e\u5927\u529b\u8dd1\u5806\u4f18\u5316dij\u5373\u53ef\u3002\u53ef\u4ee5\u7528pair\u52a0\u4f2a\u51fd\u6570\u5957STL\u3002
\n\u7279\u522b\u8981\u6ce8\u610f\u662f\u5c0f\u6839\u5806\u3002<\/p>\n
#include<iostream>\r\n#include<cstdio>\r\n#include<queue>\r\n#include<cstring>\r\n#include<vector>\r\nusing namespace std;\r\n#define Min(_A,_B) ((_A)<(_B)?(_A):(_B)) \r\n\r\nstruct ee{\r\n int v;int w;int nxt;\r\n}e[100005];\r\nint h[10005],et=0,f[10005][12],n,m,k,s,t;\r\ninline void add(const int &u,const int &v,const int &w){\r\n e[++et]=(ee){v,w,h[u]};\r\n h[u]=et;\r\n}\r\ntypedef pair<int,int> pii;\r\nstruct cmp{\r\n\tbool operator ()(const pii &A,const pii &B){\r\n\t\treturn f[A.first][A.second]>f[B.first][B.second];\r\n\t}\r\n};\r\npriority_queue<pii,vector<pii>,cmp> q;\r\nvoid bfs(int s){\r\n pii p(s,0);\r\n q.push(p);\r\n while(!q.empty()){\r\n p=q.top();\r\n q.pop();\r\n for(int i=h[p.first];i;i=e[i].nxt){\r\n if(f[e[i].v][p.second]>f[p.first][p.second]+e[i].w){\r\n f[e[i].v][p.second]=f[p.first][p.second]+e[i].w;\r\n q.push((pii){e[i].v,p.second});\r\n }\r\n if(p.second+1<=k){\r\n if(f[e[i].v][p.second+1]>f[p.first][p.second]){\r\n f[e[i].v][p.second+1]=f[p.first][p.second];\r\n q.push((pii){e[i].v,p.second+1});\r\n }\r\n }\r\n }\r\n }\r\n}\r\nvoid init(){\r\n scanf(\"%d%d%d\",&n,&m,&k);\r\n scanf(\"%d%d\",&s,&t);\r\n memset(f,0x3f,sizeof(f));\r\n int u,v,w;\r\n for(int i=1;i<=m;++i){\r\n scanf(\"%d%d%d\",&u,&v,&w);\r\n if(u==v){\r\n continue;\r\n }\r\n add(u,v,w);\r\n add(v,u,w);\r\n }\r\n for(int i=0;i<=k;++i){\r\n f[s][i]=0;\r\n }\r\n bfs(s);\r\n int ans=0x3f3f3f3f;\r\n for(int i=0;i<=k;++i){\r\n ans=Min(ans,f[t][i]);\r\n }\r\n printf(\"%d\",ans);\r\n \r\n}\r\nint main(){\r\n init();\r\n return 0;\r\n}<\/code><\/pre>\n <\/p>\n","protected":false},"excerpt":{"rendered":"
\u9996\u5148\u770b\u5230\u70b9\u6570\uff0c\u5c31\u8003\u8651\u62c6\u70b9\u3002 \u628a\u6bcf\u4e00\u4e2a\u70b9\u62c6\u6210k\u4e2a\u70b9\uff0c\u5206\u522b\u8868\u793a\u5df2\u7ecf\u5403\u4e86k\u6b21\u514d\u8d39\u5348\u9910\u7684\u8ddd\u79bb\u3002 \u7136\u540e\u5927\u529b\u8dd1\u5806\u4f18\u5316dij … <\/p>\n