tuki2501

abc224_d.cpp

Dec 5th, 2021
505
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. typedef long long ll;
  5.  
  6. signed main() {
  7.   cin.tie(0)->sync_with_stdio(0);
  8.   if (fopen("in", "r")) {
  9.     freopen("in", "r", stdin);
  10.   }
  11.   vector<vector<int>> adj(10);
  12.   int m; cin >> m;
  13.   for (int i = 0; i < m; i++) {
  14.     int u, v;
  15.     cin >> u >> v;
  16.     adj[u].push_back(v);
  17.     adj[v].push_back(u);
  18.   }
  19.   vector<int> a(10);
  20.   for (int i = 1; i <= 8; i++) {
  21.     int x; cin >> x;
  22.     a[x] = i;
  23.   }
  24.   int emp = -1;
  25.   for (int i = 1; i <= 9; i++) {
  26.     if (!a[i]) {
  27.       emp = i;
  28.       break;
  29.     }
  30.   }
  31.   set<vector<int>> vst;
  32.   queue<tuple<vector<int>,int,int>> q;
  33.   q.push({a, emp, 0});
  34.   while (q.size()) {
  35.     vector<int> a = get<0>(q.front());
  36.     int emp = get<1>(q.front());
  37.     int cnt = get<2>(q.front());
  38.     q.pop();
  39.     if (vst.count(a)) continue;
  40.     vst.insert(a);
  41.     bool flag = true;
  42.     for (int i = 1; i <= 9; i++) {
  43.       if (i != emp && i != a[i]) {
  44.         flag = false;
  45.         break;
  46.       }
  47.     }
  48.     if (flag) {
  49.       cout << cnt << '\n';
  50.       return 0;
  51.     }
  52.     for (auto &j : adj[emp]) {
  53.       swap(a[emp], a[j]);
  54.       q.push({a, j, cnt + 1});
  55.       swap(a[emp], a[j]);
  56.     }
  57.   }
  58.   cout << -1 << '\n';
  59. }
RAW Paste Data