fork download 
  1. #include "bits/stdc++.h"
  2.  
  3. using namespace std;
  4.  
  5. #define  f first
  6. #define  lgn 25
  7. #define  endl '\n'
  8. #define  sc second
  9. #define  N (int)2e5+5
  10. #define  sz(x) x.size()
  11. #define  int long long int
  12. #define  ld long double
  13. #define  vi vector<int>
  14. #define  vs vector<string>
  15. #define  vc vector<char>
  16. #define  mii map<int,int>
  17. #define  pii pair<int,int>
  18. #define  vpii vector<pii>
  19. #define  test(x) while(x--)
  20. #define  pb push_back
  21. #define  eb emplace_back
  22. #define  pq priority_queue
  23. #define  mod 1000000007
  24. #define  fo(i,a,n) for(int i=a;i<n;i++)
  25. #define  rfo(i,n,a) for(int i=n;i>=a;i--)
  26. #define  mst(a,v,n) fo(i,0,n) a[i]=v
  27. #define  all(x) begin(x),end(x)
  28. #define  allr(x) rbegin(x),rend(x)
  29. #define  rev(x) reverse(begin(x),end(x))
  30. #define  db(x) cout<<#x <<" : "<< x <<endl;
  31. #define time() cerr << "Time : " << (double)clock() / (double)CLOCKS_PER_SEC << "s\n"
  32.  
  33. const int inf = 0x3f3f3f3f;
  34. const int INF = 0x3f3f3f3f3f3f3f3f;
  35.  
  36. int n,m,k,q,e,src;
  37. vpii adj[N];
  38. int vis[N],par[N],a[N],dis[N];
  39.  
  40. void bfs()
  41. {
  42. 	queue<pii> q;
  43.  
  44. 	fo(i,1,n+1) dis[i] = inf,vis[i] = 0; // Assigning distance and visited array
  45.  
  46. 	dis[src] = 0; // making starting point distance as zero
  47.  
  48. 	q.push({src,dis[src]}); // pushing source in queue
  49. 	vis[src] = 1; // marking source as visited
  50.  
  51. 	while(!q.empty())
  52. 	{
  53. 		auto u = q.front(); // u is of  datatype pair<int,int>
  54. 							// u.f denotes the vertex and u.sc denotes the distance
  55. 		q.pop();
  56.  
  57. 		for ( auto i : adj[u.f] ) // traversing all direct edges in adjacency list
  58. 		{
  59.  
  60. 			auto v = i.f; // v is vertex directly connceted 
  61. 			int w = i.sc; // weight of edges u-v
  62.  
  63. 			if( vis[v] ) continue;
  64.  
  65. 			if( dis[v] > dis[u.f] + w ) // if distance from u to v is smaller than the  distance then update it
  66. 			{
  67. 				dis[v] = dis[u.f] + w; 
  68. 				q.push({v,dis[v]});
  69. 				vis[v] = 1;
  70. 			}
  71. 		}
  72. 	}
  73.  
  74. }
  75.  
  76. void go()
  77. {
  78. 	cin>>n>>e;
  79.  
  80. 	fo(i,0,e) // loop for inputing edges
  81. 	{
  82. 		int u,v;
  83. 		cin>>u>>v;
  84. 		adj[u].pb({v,6}); // edge from u to v 
  85. 		adj[v].pb({u,6});// edge from v to u
  86. 	}
  87.  
  88. 		cin>>src; // inputing source
  89.  
  90. 		bfs(); // calling bfs ( source is global as src so no need to pass in bfs)
  91.  
  92. 		fo(i,1,n+1)
  93. 		{
  94. 			if( i == src ) continue; // source is not required to print
  95. 			if( dis[i] != inf ) cout << dis[i] <<' ';
  96. 			else cout << -1 << ' ';
  97. 		}
  98. 		cout << endl ;
  99.  
  100. 		fo(i,1,n+1) adj[i].clear(); // clearing adjacency list for next test case
  101.  
  102. }
  103.  
  104. int32_t main()
  105. {	
  106. 	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  107. 	int t=1; 
  108. 	cin>>t;
  109. 	test(t) go();
  110. }
Success #stdin #stdout 0s 8204KB
comments (?)
stdin 
1
5 3
1 2
1 3
3 4
1
stdout 
6 6 12 -1
https://ideone.com/WDMD8K
language:
C++14 (gcc 8.3)
created:
6 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!