fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define loop(a,b,c) for(int a=b;a<c;a++)
  3. #define loopm(a,b) for(int a=b;a>=0;a--)
  4. #define pb push_back
  5. #define mp make_pair
  6. #define fi first
  7. #define se second
  8. #define f front()
  9. #define b back()
  10. #define sz(v) v.size()
  11. #define all(v) v.begin(),v.end()
  12. #define reset(a,b) memset(a,b,sizeof a)
  13.  
  14. using namespace std;
  15. typedef long long ll;
  16. typedef unsigned long long ull;
  17. typedef vector<int> vi;
  18. typedef pair<int,int> ii;
  19. typedef vector<ii> vii;
  20. typedef pair<int,ii> iii;
  21. typedef vector<iii> viii;
  22. typedef map<int,int> mii;
  23. typedef map<string,int> msi;
  24.  
  25. //templates end here
  26.  
  27. vii v[10001];
  28.  
  29. int main()
  30. {
  31. 	int N;
  32. 	int T;
  33. 	scanf("%d",&T);
  34. 	loop(i,1,T+1)
  35. 	{
  36. 		int maks=-1;
  37. 		int Q;
  38. 		loop(j,1,10001)v[j].clear();
  39. 		scanf("%d",&N);
  40. 		loop(j,0,N)
  41. 		{
  42. 			int idx,a,M;
  43. 			scanf("%d",&M);
  44. 			loop(k,0,M)
  45. 			{
  46. 				scanf("%d",&a);
  47. 				maks=max(maks,a);
  48. 				if(k==0)idx=a;
  49. 				else
  50. 				{
  51. 					v[idx].pb(mp(a,1));
  52. 					v[a].pb(mp(idx,1));
  53. 					idx=a;
  54. 				}
  55. 			}
  56. 		}
  57. 		int g,h;
  58. 		scanf("%d",&Q);
  59. 		vi ans;
  60. 		vi bfs;
  61. 		loop(j,0,Q)
  62. 		{
  63. 			bool cek=0;
  64. 			bfs.assign(maks+1,-1);
  65. 			scanf("%d %d",&g,&h);
  66. 			if(sz(v[g])==0||sz(v[h])==0)ans.pb(-1);
  67. 			else
  68. 			{
  69. 				queue<ii> pq;
  70. 				pq.push(mp(0,g));
  71. 				while(!pq.empty())
  72. 				{
  73. 					ii z=pq.front();
  74. 					pq.pop();
  75. 					loop(k,0,sz(v[z.se]))
  76. 					{
  77. 						if(bfs[v[z.se][k].fi]==-1)
  78. 						{
  79. 							bfs[v[z.se][k].fi]=1;
  80. 							pq.push(mp(z.fi+1,v[z.se][k].fi));
  81. 						}
  82. 					}
  83. 					if(z.se==h)
  84. 					{
  85. 						ans.pb(z.fi);cek=1;break;	
  86. 					}
  87. 				}	
  88. 				if(!cek)ans.pb(-1);
  89. 			}
  90. 		}
  91. 		printf("Case #%d:\n",i);
  92. 		loop(j,0,sz(ans))cout<<ans[j]<<endl;
  93. 		ans.clear();
  94. 	}
  95. }
  96.  
Success #stdin #stdout 0s 3576KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/mksXts
language:
C++ (gcc 8.3)
created:
8 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!