dns网站卫士 收录,郑州百度seo网站优化,wordpress免费杂志模板,做游戏音频下载网站题意#xff1a;给你n-1条边#xff0c;然后没两个节点的距离按照递增的顺序#xff0c;求出前k项的和。 官方题解#xff1a; 把所有边(u,v) 以及(v,u)放入一个队列#xff0c;队列每弹出一个元素(u,v)#xff0c;对于所有与u相邻的点w#xff0c;如果w!v#xff0c;就… 题意给你n-1条边然后没两个节点的距离按照递增的顺序求出前k项的和。 官方题解 把所有边(u,v) 以及(v,u)放入一个队列队列每弹出一个元素(u,v)对于所有与u相邻的点w如果w!v就把(w,u)入队。这样就能一个一个生成前K小的距离。 注意到每条边实际上会入队两次只要把K翻倍且把ans除2即可时间复杂度为O(nK) 这里只是实现一下而已。 代码 #pragma comment(linker, /STACK:1024000000,1024000000)
#include iostream
#include cstdio
#include cstring
#include cstdlib
#include cmath
#include algorithm
#include queue
using namespace std;
#define N 100007struct node
{int u,v,d;node(int _u,int _v,int _d):u(_u),v(_v),d(_d){}node(){}
};
struct Edge{int v,next;
}G[2*N];
int ans,k,tot,head[N];
queuenode q;void addedge(int u,int v)
{G[tot].v v;G[tot].next head[u];head[u] tot;
}void bfs()
{int cnt 0;while(!q.empty()){node tmp q.front();q.pop();int u tmp.u, v tmp.v, d tmp.d;if(cnt k) break;for(int ihead[u];i!-1;iG[i].next){int vv G[i].v;if(vv ! v){ans d1;cnt;q.push(node(vv,u,d1));}if(cnt k) break;}if(cnt k) break;}
}int main()
{int t,n,u,v,i;scanf(%d,t);while(t--){while(!q.empty()) q.pop();scanf(%d%d,n,k);tot 0;memset(head,-1,sizeof(head));for(i1;in;i) q.push(node(i,i,0));for(i1;in;i){scanf(%d%d,u,v);addedge(u,v);addedge(v,u);}k * 2;ans 0;bfs();coutans/2endl;}return 0;
} View Code 转载于:https://www.cnblogs.com/whatbeg/p/4087765.html
