fork(1) download
copy 
  1. #include <iostream>
  2. #include <cstring>
  3. #include <cstdio>
  4. #include <algorithm>
  5. #include<set>
  6. #include <cmath>
  7. #include<sstream>
  8. #include<queue>
  9. #include<vector>
  10. #include<stdio.h>
  11. #include<stack>
  12. #include<deque>
  13. #include<bitset>
  14. #include<string>
  15. #include<cstdio>
  16. #include<map>
  17. #include<iterator>
  18. #include<iomanip>
  19. #define prfs(x) printf("%s\n",x.c_str())
  20. #define prfi(x) printf("%d\n",x);
  21. #define sfi(X) scanf("%d",&X);
  22. #define lop(i,n) for (int i = 0 ; i < n ;i++)
  23. #define blop(i,n) for(int i = n-1 ; i>=0;i--)
  24. #define M_P make_pair
  25. #define All(X) (X).begin(),(X).end()
  26. #define SZ(n) (int)(n).size()
  27. #define voi vector<int>
  28. #define vos vector<string>
  29. #define vob vector<bool>
  30. #define vovi vector<vector<int > >
  31. #define vob vector<bool>
  32. #define ll long long 
  33. using namespace std;
  34. vector<int> AdjList[333];
  35. int parent[333];
  36. bool vis[333];
  37. int s, t;
  38. void printPath(int u,int p) {
  39. 	if (u == p) 
  40. 	{ printf("%d", p);
  41. 	return; }
  42. 	printPath(parent[u],p);
  43. 	printf(" %d",u);
  44. }
  45. bool BFS(int n,int tar) {
  46. 	lop(i, 330)vis[i] = 0,parent[i] = i;
  47. 	queue<int> q;
  48. 	q.push(n);
  49. 	while (!q.empty()) {
  50. 		int u = q.front(); q.pop();
  51. 		if (u == tar)return 1;
  52. 		vis[u] = 1;
  53. 		sort(All(AdjList[u - 1]));
  54. 		for (int i = 0; i < AdjList[u].size(); i++) {
  55. 			int v = AdjList[u][i];
  56. 			if (!vis[v]) {
  57. 				parent[v] = u;
  58. 				q.push(v);
  59. 				vis[v] = 1;
  60. 			}
  61. 		}
  62. 	}
  63. 	return 0;
  64. }
  65. int main()
  66. {
  67. 	//freopen("src.txt", "r", stdin);
  68. 	int n;
  69. 	while (scanf("%d", &n) == 1) {
  70. 		for (int i = 0; i < 305;i++)AdjList[i].clear();
  71. 		string ss;
  72. 		for (int j = 1; j <= n; j++) {
  73. 			cin >> ss;
  74. 			for (int i = 2; i < ss.size(); i++) {
  75. 				string A = "";
  76. 				for (; ss[i] != ',' && i < ss.size();i++) {
  77. 					A += ss[i];
  78. 				}
  79. 				if (A.size())
  80. 					AdjList[j].push_back(atoi(A.c_str()));
  81. 			}
  82. 		}
  83. 		int m;scanf("%d", &m);
  84. 		printf("-----\n");
  85. 		for (int j = 0;j < m; j++) {
  86. 			scanf("%d%d", &s, &t);
  87. 			if (BFS(s, t)) {
  88. 				printPath(t, s);
  89. 				printf("\n");
  90. 			}
  91. 			else {
  92. 				printf("connection impossible\n");
  93. 			}
  94. 		}
  95.  
  96.  
  97. 	}
  98. 	return 0;
  99. }
  100.  
Success #stdin #stdout 0s 3472KB
comments (?)
stdin
copy 
6
1-2,3,4
2-1,3
3-1,2,5,6
4-1,5
5-3,4,6
6-3,5
6
1 6
1 5
2 4
2 5
3 6
2 1
10
1-2
2-
3-4
4-8
5-1
6-2
7-3,9
8-10
9-5,6,7
10-8
3
9 10
5 9
9 2
stdout
copy 
-----
1 3 6
1 3 5
2 1 4
2 3 5
3 6
2 1
-----
9 7 3 4 8 10
connection impossible
9 6 2
https://ideone.com/nFDvYI
language:
C++14 (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!