求某个人的n度好友：
对于一个小集体（一组数据），a是b的好友，友好度为x; b是c的好友，友好度为y;且a和c不是好友，那么称c为a的2度好友，友好度为x+y； b为a的1度好友，友好度为x;
现在输入数据：
第1行：T，代表总共有n组数据，如下面为2；
第2~3行：分别输入第1组数据的不同参数，
第2行：m , i , n;
m=10代表这组有10个人，则每个人的编号为0~9；
i=5 代表求编号为5的人的好友关系；
n=2 代表求5号的2度好友，没有输出-1；如果有的话，则按照友好度降序排列，如果友好度相同，则按照人的编号升序排列；
第3行：第一个数字k=13表示第1组总共有13个朋友关系，0 3 5代表0号和3号的友谊度为5，依次类推；
按顺序输出：第i号的n度好友，如果T等于2那么应该输出两组关系；
2 10 5 2 13 0 3 5 ...省略后面
C++代码：
#include<iostream> #include<vector> #include<string> #include<queue> #include<algorithm> using namespace std; bool cmp(vector<int> a,vector<int> b){ return a[1]>b[1]; } int main(){ int T; cin>>T; for(int id=0;id<T;id++){ int m,i,n; cin>>m>>i>>n; int k; cin>>k; //朋友圈图初始化 vector<vector<int> > g(m,vector<int>(m,0)); for(int x=0;x<k;x++){ int a,b,w; cin>>a>>b>>w; g[a][b]=g[b][a]=w; } vector<int> visit(m,0); queue<int> q; //初始化1度好友 for(int x=0;x<m;x++){ if(g[i][x]!=0){ q.push(x); visit[x]=g[i][x]; } } //广度优先搜索 //第一层，找n度好友 for(int x=1;x<n;x++){ int len=q.size(); //第二层，把当前度的好友找完，共y个好友； for(int y=0;y<len;y++){ int a=q.front(); q.pop(); //第三层，对当前第x度寻找所有下一个度的好友 for(int z=0;z<m;z++){ if(z!=i && g[a][z]!=0 && visit[z]==0){ q.push(z); visit[z]=visit[a]+g[a][z]; } if(visit[z]!=0 && visit[z]<visit[a]+g[a][z]) visit[z]=visit[a]+g[a][z]; } } } vector<int> ndf; if(q.size()==0){ cout<<-1<<endl;continue; }else{ while(!q.empty()){ ndf.push_back(q.front()); q.pop(); } } int max_x=ndf.size(); vector<vector<int> > res; sort(ndf.begin(),ndf.end()); for(int x=0;x<max_x;x++){ vector<int> cell; cell.push_back(ndf[x]); cell.push_back(visit[ndf[x]]); res.push_back(cell); } sort(res.begin(),res.end(),cmp); for(int x=0;x<max_x;x++){ cout<<res[x][0]<<" "; } cout<<endl; } return 0; } /* 2 10 5 2 13 0 3 5 0 4 9 0 6 8 0 7 5 1 2 6 1 6 3 2 9 7 3 4 3 3 5 3 3 8 3 3 9 3 5 8 9 7 8 9 10 0 2 13 0 3 5 0 4 9 0 6 8 0 7 5 1 2 6 1 6 3 2 9 7 3 4 3 3 5 3 3 8 3 3 9 3 5 8 9 7 8 9 */
原文：https://www.cnblogs.com/joelwang/p/11440510.html