Advertisement
Dzham

Untitled

Apr 22nd, 2018
112
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 7.40 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. #include <iterator>
  5. #include <unordered_map>
  6. #include <unordered_set>
  7. #include <string>
  8. #include <set>
  9. #include <queue>
  10.  
  11. class Graph {
  12. private:
  13. int size_g;
  14. std::vector<std::vector<int>> data;
  15. std::vector<int> fleas;
  16. std::vector<int> used;
  17. std::vector<std::vector<int>> coordinates;
  18. int size_H;
  19. int size_W;
  20.  
  21. public:
  22. std::vector<bool> isused;
  23. std::vector<int> distance;
  24.  
  25. explicit Graph(int n) {
  26. data.resize(n);
  27. isused.resize(n);
  28. size_g = n;
  29. }
  30.  
  31. Graph(int h, int w) {
  32. size_g = h * w;
  33. size_H = h;
  34. size_W = w;
  35. isused.resize(h * w);
  36. coordinates.resize(h * w);
  37. int counter = 0;
  38. for (int i = 0; i < h; i++) {
  39. for (int j = 0; j < w; j++) {
  40. coordinates[counter].push_back(i);
  41. coordinates[counter].push_back(j);
  42. counter++;
  43. }
  44. }
  45. }
  46.  
  47. void insert(int a, int b) {
  48. if (a != b) {
  49. data[a - 1].push_back(b);
  50. data[b - 1].push_back(a);
  51. }
  52. }
  53.  
  54. explicit Graph(std::vector<std::vector<int>> graph) {
  55. isused.resize(graph.size());
  56. size_g = graph.size();
  57. data = graph;
  58. }
  59.  
  60. void printgraph() {
  61. for (int i = 0; i < data.size(); i++) {
  62. for (auto j : data[i]) {
  63. std::cout << j << " ";
  64. }
  65. std::cout << '\n';
  66. }
  67. }
  68.  
  69. std::vector<int> neighbours(int a) {
  70. int y = coordinates[a][0];
  71. int x = coordinates[a][1];
  72. std::vector<int> result;
  73. int n1 = a + 2 * size_W + 1;
  74. int n2 = a + 2 * size_W - 1;
  75. int n3 = a - 2 * size_W + 1;
  76. int n4 = a - 2 * size_W - 1;
  77. int n5 = a + size_W + 2;
  78. int n6 = a + size_W - 2;
  79. int n7 = a - size_W + 2;
  80. int n8 = a - size_W - 2;
  81. bool check1 = y + 2 < size_H && x + 1 < size_W;
  82. bool check2 = y + 2 < size_H && x - 1 > -1;
  83. bool check3 = y - 2 > -1 && x + 1 < size_W;
  84. bool check4 = y - 2 > -1 && x - 1 > -1;
  85. bool check5 = y + 1 < size_H && x + 2 < size_W;
  86. bool check6 = y + 1 < size_H && x - 2 > -1;
  87. bool check7 = y - 1 > -1 && x + 2 < size_W;
  88. bool check8 = y - 1 > -1 && x - 2 > -1;
  89. if (check1 && !isused[n1]) {
  90. result.push_back(n1);
  91. }
  92. if (check2 && !isused[n2]) {
  93. result.push_back(n2);
  94. }
  95. if (check3 && !isused[n3]) {
  96. result.push_back(n3);
  97. }
  98. if (check4 && !isused[n4]) {
  99. result.push_back(n4);
  100. }
  101. if (check5 && !isused[n5]) {
  102. result.push_back(n5);
  103. }
  104. if (check6 && !isused[n6]) {
  105. result.push_back(n6);
  106. }
  107. if (check7 && !isused[n7]) {
  108. result.push_back(n7);
  109. }
  110. if (check8 && !isused[n8]) {
  111. result.push_back(n8);
  112. }
  113. return result;
  114. }
  115.  
  116. int bfstrains(std::set<int> starts, std::set<int> finals) {
  117. std::queue<int> vert;
  118. std::vector<int> result(size_g, -1);
  119. for (auto i : starts) {
  120. vert.push(i);
  121. isused[i - 1] = true;
  122. result[i - 1] = 0;
  123. }
  124. while (vert.size() != 0) {
  125. int s = vert.front();
  126. vert.pop();
  127. std::vector<int> child = data[s - 1];
  128. for (auto into : child) {
  129. if (!isused[into - 1]) {
  130. isused[into - 1] = true;
  131. vert.push(into);
  132. result[into - 1] = result[s - 1] + 1;
  133. }
  134. }
  135. }
  136. int answer = 100000000;
  137. for (auto i : finals) {
  138. if (result[i - 1] == -1) {
  139. answer = -1;
  140. break;
  141. } else {
  142. if (result[i - 1] < answer) {
  143. answer = result[i - 1];
  144. }
  145. }
  146. }
  147. return answer;
  148. }
  149.  
  150. int bfschess(int start, std::vector<int> fleas) {
  151. std::queue<int> vert;
  152. std::vector<int> result(size_g, -1);
  153. vert.push(start);
  154. isused[start] = true;
  155. result[start] = 0;
  156. while (vert.size() != 0) {
  157. int s = vert.front();
  158. vert.pop();
  159. std::vector<int> child = neighbours(s);
  160. for (auto into : child) {
  161. if (!isused[into]) {
  162. isused[into] = true;
  163. vert.push(into);
  164. result[into] = result[s] + 1;
  165. }
  166. }
  167. }
  168. int answer = 0;
  169. for (auto i : fleas) {
  170. if (result[i] == -1) {
  171. answer = -1;
  172. break;
  173. } else {
  174. answer += result[i];
  175. }
  176. }
  177. return answer;
  178. }
  179.  
  180. void Dijkstra(int a, int b) {
  181. isused.clear();
  182. isused.resize(size_g);
  183. std::cout << isused.size();
  184. isused[a - 1] = true;
  185. std::vector<int> result;
  186. std::vector<int> way;
  187. std::vector<std::vector<int>> ways;
  188. ways.resize(size_g);
  189. result = data[a - 1];
  190. int v;
  191. for (int j = 0; j < size_g; j++) {
  192. v = -1;
  193. std::cout << "abc";
  194. for (int i = 0; i < size_g; i++) {
  195. if (!isused[i] && ((v == -1) || result[v] > result[i])) {
  196. v = i;
  197. }
  198. }
  199. if (v == -1) {
  200. v = size_g - 1;
  201. }
  202. std::cout << "dfc";
  203. isused[v] = true;
  204. for (int i = 0; i < size_g; i++) {
  205. if (result[i] > result[v] + data[i][v]) {
  206. result[i] = result[v] + data[v][i];
  207. }
  208. }
  209. std::cout << "wtf";
  210. }
  211. if (result[b - 1] <= 0 || result[b - 1] == 200000) {
  212. std::cout << -1;
  213. } else {
  214. std::cout << result[b - 1] << "\n";
  215. }
  216. }
  217. };
  218.  
  219. using namespace std;
  220.  
  221. bool empty_intersection(const set<int>& x, const set<int>& y) {
  222. set<int>::const_iterator i = x.begin();
  223. set<int>::const_iterator j = y.begin();
  224. while (i != x.end() && j != y.end()) {
  225. if (*i == *j)
  226. return false;
  227. else if (*i < *j)
  228. ++i;
  229. else
  230. ++j;
  231. }
  232. return true;
  233. }
  234.  
  235. int main() {
  236. int N, M, P, a;
  237. std::cin >> N >> M;
  238. std::vector<std::vector<int>> dat;
  239. std::unordered_map<int, std::set<int>> stations;
  240. dat.resize(M);
  241. std::vector<std::set<int>> lines;
  242. for (int i = 0; i < M; i++) {
  243. std::set<int> s;
  244. std::cin >> P;
  245. for (int j = 0; j < P; j++) {
  246. std::cin >> a;
  247. s.insert(a);
  248. stations[a].insert(i + 1);
  249. }
  250. for (int j = 0; j < lines.size(); j++) {
  251. if (!empty_intersection(s, lines[j])) {
  252. dat[j].push_back(lines.size() + 1);
  253. dat[lines.size()].push_back(j + 1);
  254. }
  255. }
  256. lines.push_back(s);
  257. }
  258. Graph graph(dat);
  259. std::cin >> P >> a;
  260. if (!empty_intersection(stations[P], stations[a])) {
  261. std::cout << 0;
  262. } else {
  263. std::cout << graph.bfstrains(stations[P], stations[a]);
  264. }
  265. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement