SHARE
TWEET

Untitled

lalalalalalalaalalla Aug 30th, 2019 (edited) 72 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /*
  2. ЗАПУСКАЕМ
  3. ░ГУСЯ░▄▀▀▀▄░РАБОТЯГУ░░
  4. ▄███▀░◐░░░▌░░░░░░░
  5. ░░░░▌░░░░░▐░░░░░░░
  6. ░░░░▐░░░░░▐░░░░░░░
  7. ░░░░▌░░░░░▐▄▄░░░░░
  8. ░░░░▌░░░░▄▀▒▒▀▀▀▀▄
  9. ░░░▐░░░░▐▒▒▒▒▒▒▒▒▀▀▄
  10. ░░░▐░░░░▐▄▒▒▒▒▒▒▒▒▒▒▀▄
  11. ░░░░▀▄░░░░▀▄▒▒▒▒▒▒▒▒▒▒▀▄
  12. ░░░░░░▀▄▄▄▄▄█▄▄▄▄▄▄▄▄▄▄▄▀▄
  13. ░░░░░░░░░░░▌▌░▌▌░░░░░
  14. ░░░░░░░░░░░▌▌░▌▌░░░░░
  15. ░░░░░░░░░▄▄▌▌▄▌▌░░░░░
  16. */
  17.  
  18.  
  19. #include <iostream>
  20. #include <vector>
  21. #include <string>
  22. #include <iomanip>
  23. #include <queue>
  24. #include <cmath>
  25. #include <algorithm>
  26. #include <tuple>
  27. #include <iomanip>
  28. #include <stdio.h>
  29. #include <numeric>
  30. #include <map>
  31. #include <bitset>
  32. #include <set>
  33. #include <stack>
  34. #include <queue>
  35.  
  36. //#define int long long
  37. #define ll long long
  38. #define ull unsigned long long
  39. #define all(a) a.begin(), a.end()
  40. #define pii pair<int, int>
  41. #define pb push_back
  42. #define ld long double
  43.  
  44. //#pragma GCC optimize("O3");
  45.  
  46. using namespace std;
  47.  
  48. const int INF = 2e9;
  49. //const int mod = 2600000069;
  50. //const int p = 179;
  51.  
  52. int n, r, a1, b1, a2, b2;
  53. vector<set<int>> g;
  54. vector<vector<pii>> g1(13000);
  55. set<pii> s;
  56. vector<int> d(13000, INF), p(13000, INF);
  57. int v;
  58.  
  59. int one(int a, int b) {
  60.     return (a << 7) + b;
  61. }
  62.  
  63. void Dijkstra(int start) {
  64.     s.insert({0, start});
  65.     while (!s.empty()) {
  66.         v = s.begin()->second;
  67.         s.erase(s.begin());
  68.         for (auto u: g1[v]) {
  69.             if (d[u.first] == d[v] + u.second) {
  70.                 p[u.first] = min(p[u.first], p[v] + 1);
  71.             } else if (d[u.first] > d[v] + u.second) {
  72.                 s.erase({d[u.first], u.first});
  73.                 d[u.first] = d[v] + u.second;
  74.                 p[u.first] = p[v] + 1;
  75.                 s.insert({d[u.first], u.first});
  76.             }
  77.         }
  78.     }
  79. }
  80.  
  81. signed main() {
  82.     ios_base::sync_with_stdio(0);
  83.     cin.tie(0);
  84.     cout.tie(0);
  85.     cin >> n >> r >> a1 >> b1 >> a2 >> b2;
  86.     a1--;b1--;a2--;b2--;
  87.     g.resize(n);
  88.     int x, y, start = one(a1, b1), finish = one(a2, b2);
  89.     for (int i = 0; i < n; i++) g[i].insert(i);
  90.     for (int i = 0; i < r; i++) {
  91.         cin >> x >> y;
  92.         x--;
  93.         y--;
  94.         g[x].insert(y);
  95.         g[y].insert(x);
  96.     }
  97.     for (int s1 = 0; s1 < n; s1++) {
  98.         for (int e1 = 0; e1 < n; e1++) {
  99.             if (s1 == e1) continue;
  100.             for (auto s2: g[s1]) {
  101.                 for (auto e2: g[e1]) {
  102.                     /*
  103.                      * 1 - первого отрезка нет
  104.                      * 2 - второго отрезка нет
  105.                      * 3 - один отрезок с разными концами
  106.                      * 4 - один отрезок
  107.                     */
  108.                     if (!g[s1].count(e1) || !g[s2].count(e2) || (s1 == e2 && s2 == e1) || (s1 == s2 && e1 == e2)) continue;
  109.                     if (s1 != s2 && e1 != e2) {
  110.                         g1[one(s1, e1)].pb({one(s2, e2), 2});
  111.                     } else {
  112.                         g1[one(s1, e1)].pb({one(s2, e2), 1});
  113.                     }
  114.                 }
  115.             }
  116.         }
  117.     }
  118.     d[start] = 0;
  119.     p[start] = 1;
  120.     Dijkstra(start);
  121.     cout << d[finish] << " " << p[finish];
  122. }
  123. /*
  124. 4 5 1 2 2 1
  125. 1 2
  126. 2 3
  127. 3 4
  128. 4 1
  129. 1 3
  130. -> 3 3
  131.  
  132. 4 4 1 4 3 4
  133. 1 2
  134. 2 3
  135. 3 4
  136. 1 4
  137. -> 4 3
  138.  
  139. 5 5 1 2 5 4
  140. 1 2
  141. 2 3
  142. 3 4
  143. 4 5
  144. 2 5
  145. -> 4 3
  146.  
  147. 6 7 1 2 6 5
  148. 1 2
  149. 2 3
  150. 3 4
  151. 4 1
  152. 4 6
  153. 5 6
  154. 5 3
  155. -> 4 3
  156. */
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top