wordpress页面如何排序,网站优化推广软件,做网络推广一个月的收入,重庆网站建设设计公司时间限制#xff1a; 3S空间限制#xff1a; 256M具体思路:DPf[i][j][k]表示1-i,前L条路上用了 j条,L后的路上换了k条的最小代价枚举一下L就有了一个复杂度O(nlognk^3)的做法AC代码#includebits/stdc.h
using namespace std;
#define INF 100000000
#define P pair 3S 空间限制 256M 具体思路:DP f[i][j][k]表示1-i,前L条路上用了 j条,L后的路上换了k条的最小代价 枚举一下L就有了一个复杂度O(nlognk^3)的做法 AC代码 #includebits/stdc.h
using namespace std;
#define INF 100000000
#define P pairint,int
const int M200010;
int n,i,j,m,k,top1,L,mogic;
int first[M],next[M],to[M],last[M],len[M],f[100][200][50],ord[M];
bool vis[M*3];
struct E{int x,y,w;}e[M]; queuePq; inline bool cmp(const Ea,const Eb){return a.wb.w;} int ans2100000000,base0; void add(int x,int y,int z,int num) { top,to[top]y;len[top]z;ord[top]num; if(first[x]0)first[x]top;else next[last[x]]top; last[x]top; } void PUSH(int x,int y,int z,int w) { if(yL||zmogic)return; if(f[x][y][z]w)return; q.push(P(f[x][y][z]w,(x13)|(y5)|(z))); } int main() { scanf(%d%d%d,n,m,mogic); for(i1;im;i)scanf(%d%d%d,e[i].x,e[i].y,e[i].w); sort(e1,e1m,cmp); for(i1;im;i)add(e[i].x,e[i].y,e[i].w,i),add(e[i].y,e[i].x,e[i].w,i); for(L0;Lm;L) { basee[L].w; if(baseans)break; for(i1;in;i)for(j0;jL;j)for(k0;kmogic;k)f[i][j][k]INF; memset(vis,0,sizeof(vis)); PUSH(1,0,0,base); while(!q.empty()) { P TOPq.front();q.pop(); int zTOP.second31;TOP.second5; int yTOP.second255;TOP.second8; int xTOP.second; if(f[x][y][z]TOP.first)continue; for(ifirst[x];i;inext[i]) if(ord[i]L) { PUSH(to[i],y1,z,TOP.first); }else PUSH(to[i],y,z,TOP.firste[ord[i]].w),PUSH(to[i],y,z1,TOP.first); } for(j0;jL;j)for(k0;kmogic;k)if(jkLf[n][j][k]ans)ansf[n][j][k]; } printf(%d,ans); return 0; } 转载于:https://www.cnblogs.com/Orange-User/p/8507160.html
