Maruf_Hasan

567

Dec 14th, 2018
91
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.46 KB | None | 0 0
  1. #include<stdio.h>
  2. #include<bits/stdc++.h>
  3. using namespace std;
  4. #define M 10000
  5.  
  6. int bfs(vector<int>v[M],int source,int desti)
  7. {
  8. queue<int>q;
  9. bool visited[M+5];
  10. memset(visited,false,sizeof(visited));
  11. int dist[M];
  12. memset(dist,M,sizeof(dist));
  13. q.push(source);
  14. dist[source]=0;
  15. visited[source]=true;
  16. while(!q.empty())
  17. {
  18. int u=q.front();
  19. q.pop();
  20. for(int i=0;i<v[u].size();i++)
  21. {
  22. int k=v[u][i];
  23. if(visited[k]==false)
  24. {
  25. q.push(k);
  26. visited[k]=true;
  27. dist[k]=dist[u]+1;
  28. }
  29. }
  30. }
  31.  
  32.  
  33. return dist[desti];
  34. }
  35. int main()
  36. {
  37. int n,test=1;
  38.  
  39. while(scanf("%d",&n)!=EOF)
  40. {
  41. vector<int>v[M];
  42. int i,k,j,source,desti,path,num=1;
  43. while(n--)
  44. {
  45. cin>>k;
  46. v[num].push_back(k);
  47. v[k].push_back(num);
  48. }
  49. for(i=1;i<19;i++)
  50. {
  51. cin>>n;
  52. num++;
  53. while(n--)
  54. {
  55. cin>>k;
  56. v[num].push_back(k);
  57. v[k].push_back(num);
  58. }
  59. }
  60.  
  61. int t;
  62. j=0;
  63. cin>>t;
  64. printf("Test Set #%d\n",test++);
  65. while(j<t)
  66. {
  67. cin>>source>>desti;
  68. path=bfs(v,source,desti);
  69.  
  70. printf("%d to %d: %d\n",source,desti,path);
  71. j++;
  72. }
  73. printf("\n");
  74. }
  75. return 0;
  76. }
Advertisement
Add Comment
Please, Sign In to add comment