Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <algorithm>
- #include <iterator>
- #include <unordered_map>
- #include <unordered_set>
- #include <string>
- #include <set>
- #include <queue>
- class Graph {
- private:
- int size_g;
- std::vector<std::vector<int>> data;
- std::vector<int> fleas;
- std::vector<int> used;
- std::vector<std::vector<int>> coordinates;
- int size_H;
- int size_W;
- public:
- std::vector<bool> isused;
- std::vector<int> distance;
- explicit Graph(int n) {
- data.resize(n);
- isused.resize(n);
- size_g = n;
- }
- Graph(int h, int w) {
- size_g = h * w;
- size_H = h;
- size_W = w;
- isused.resize(h * w);
- coordinates.resize(h * w);
- int counter = 0;
- for (int i = 0; i < h; i++) {
- for (int j = 0; j < w; j++) {
- coordinates[counter].push_back(i);
- coordinates[counter].push_back(j);
- counter++;
- }
- }
- }
- void insert(int a, int b) {
- if (a != b) {
- data[a - 1].push_back(b);
- data[b - 1].push_back(a);
- }
- }
- explicit Graph(std::vector<std::vector<int>> graph) {
- isused.resize(graph.size());
- size_g = graph.size();
- data = graph;
- }
- void printgraph() {
- for (int i = 0; i < data.size(); i++) {
- for (auto j : data[i]) {
- std::cout << j << " ";
- }
- std::cout << '\n';
- }
- }
- std::vector<int> neighbours(int a) {
- int y = coordinates[a][0];
- int x = coordinates[a][1];
- std::vector<int> result;
- int n1 = a + 2 * size_W + 1;
- int n2 = a + 2 * size_W - 1;
- int n3 = a - 2 * size_W + 1;
- int n4 = a - 2 * size_W - 1;
- int n5 = a + size_W + 2;
- int n6 = a + size_W - 2;
- int n7 = a - size_W + 2;
- int n8 = a - size_W - 2;
- bool check1 = y + 2 < size_H && x + 1 < size_W;
- bool check2 = y + 2 < size_H && x - 1 > -1;
- bool check3 = y - 2 > -1 && x + 1 < size_W;
- bool check4 = y - 2 > -1 && x - 1 > -1;
- bool check5 = y + 1 < size_H && x + 2 < size_W;
- bool check6 = y + 1 < size_H && x - 2 > -1;
- bool check7 = y - 1 > -1 && x + 2 < size_W;
- bool check8 = y - 1 > -1 && x - 2 > -1;
- if (check1 && !isused[n1]) {
- result.push_back(n1);
- }
- if (check2 && !isused[n2]) {
- result.push_back(n2);
- }
- if (check3 && !isused[n3]) {
- result.push_back(n3);
- }
- if (check4 && !isused[n4]) {
- result.push_back(n4);
- }
- if (check5 && !isused[n5]) {
- result.push_back(n5);
- }
- if (check6 && !isused[n6]) {
- result.push_back(n6);
- }
- if (check7 && !isused[n7]) {
- result.push_back(n7);
- }
- if (check8 && !isused[n8]) {
- result.push_back(n8);
- }
- return result;
- }
- int bfstrains(std::set<int> starts, std::set<int> finals) {
- std::queue<int> vert;
- std::vector<int> result(size_g, -1);
- for (auto i : starts) {
- vert.push(i);
- isused[i - 1] = true;
- result[i - 1] = 0;
- }
- while (vert.size() != 0) {
- int s = vert.front();
- vert.pop();
- std::vector<int> child = data[s - 1];
- for (auto into : child) {
- if (!isused[into - 1]) {
- isused[into - 1] = true;
- vert.push(into);
- result[into - 1] = result[s - 1] + 1;
- }
- }
- }
- int answer = 100000000;
- for (auto i : finals) {
- if (result[i - 1] == -1) {
- answer = -1;
- break;
- } else {
- if (result[i - 1] < answer) {
- answer = result[i - 1];
- }
- }
- }
- return answer;
- }
- int bfschess(int start, std::vector<int> fleas) {
- std::queue<int> vert;
- std::vector<int> result(size_g, -1);
- vert.push(start);
- isused[start] = true;
- result[start] = 0;
- while (vert.size() != 0) {
- int s = vert.front();
- vert.pop();
- std::vector<int> child = neighbours(s);
- for (auto into : child) {
- if (!isused[into]) {
- isused[into] = true;
- vert.push(into);
- result[into] = result[s] + 1;
- }
- }
- }
- int answer = 0;
- for (auto i : fleas) {
- if (result[i] == -1) {
- answer = -1;
- break;
- } else {
- answer += result[i];
- }
- }
- return answer;
- }
- void Dijkstra(int a, int b) {
- isused.clear();
- isused.resize(size_g);
- std::cout << isused.size();
- isused[a - 1] = true;
- std::vector<int> result;
- std::vector<int> way;
- std::vector<std::vector<int>> ways;
- ways.resize(size_g);
- result = data[a - 1];
- int v;
- for (int j = 0; j < size_g; j++) {
- v = -1;
- std::cout << "abc";
- for (int i = 0; i < size_g; i++) {
- if (!isused[i] && ((v == -1) || result[v] > result[i])) {
- v = i;
- }
- }
- if (v == -1) {
- v = size_g - 1;
- }
- std::cout << "dfc";
- isused[v] = true;
- for (int i = 0; i < size_g; i++) {
- if (result[i] > result[v] + data[i][v]) {
- result[i] = result[v] + data[v][i];
- }
- }
- std::cout << "wtf";
- }
- if (result[b - 1] <= 0 || result[b - 1] == 200000) {
- std::cout << -1;
- } else {
- std::cout << result[b - 1] << "\n";
- }
- }
- };
- using namespace std;
- bool empty_intersection(const set<int>& x, const set<int>& y) {
- set<int>::const_iterator i = x.begin();
- set<int>::const_iterator j = y.begin();
- while (i != x.end() && j != y.end()) {
- if (*i == *j)
- return false;
- else if (*i < *j)
- ++i;
- else
- ++j;
- }
- return true;
- }
- int main() {
- int N, M, P, a;
- std::cin >> N >> M;
- std::vector<std::vector<int>> dat;
- std::unordered_map<int, std::set<int>> stations;
- dat.resize(M);
- std::vector<std::set<int>> lines;
- for (int i = 0; i < M; i++) {
- std::set<int> s;
- std::cin >> P;
- for (int j = 0; j < P; j++) {
- std::cin >> a;
- s.insert(a);
- stations[a].insert(i + 1);
- }
- for (int j = 0; j < lines.size(); j++) {
- if (!empty_intersection(s, lines[j])) {
- dat[j].push_back(lines.size() + 1);
- dat[lines.size()].push_back(j + 1);
- }
- }
- lines.push_back(s);
- }
- Graph graph(dat);
- std::cin >> P >> a;
- if (!empty_intersection(stations[P], stations[a])) {
- std::cout << 0;
- } else {
- std::cout << graph.bfstrains(stations[P], stations[a]);
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement