Advertisement
luanaamorim

Untitled

Aug 17th, 2021
806
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.03 KB | None | 0 0
  1. #include <iostream>
  2. #include <queue>
  3. #include <string>
  4. #include <algorithm>
  5. #include <vector>
  6. #include <cmath>
  7. #include <iomanip>
  8. #include <map>
  9. #include <cstring>
  10. #include <set>
  11. #include <stack>
  12. #include <bitset>
  13. #define ll long long
  14. #define INF (1e15)
  15. #define MAX (int) 100000
  16. #define MOD 1000000007
  17. #define par pair<int, ll>
  18. #define all(v) v.begin(), v.end()
  19. #define sz(x) (int) ((x).size())
  20. #define esq(x) (x<<1)
  21. #define dir(x) ((x<<1)|1)
  22. #define lsb(x) (x & -x)
  23. #define W(x) cout << #x << ": " << x << endl
  24. #define Wii(x) cout << x.first << ' ' << x.second << endl
  25. #define _ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  26.  
  27. using namespace std;
  28.  
  29. int a, b, c, d, t, idx, vis[201][201][201];
  30. ll dist[MAX];
  31. vector<par> grafo[MAX];
  32. tuple<int, int, int> arr[MAX];
  33.  
  34. ll dijkstra(int x)
  35. {
  36.     priority_queue<par, vector<par>, greater<par> > fila;
  37.     for (int i = 1; i <= idx; i++)
  38.         dist[i] = INF;
  39.  
  40.     fila.push({0, vis[0][0][c]});
  41.     dist[vis[0][0][c]] = 0;
  42.     while (!fila.empty())
  43.     {
  44.         auto[d, u] = fila.top(); fila.pop();
  45.         if (d != dist[u]) continue;
  46.         for (auto[v, w] : grafo[u])
  47.         {
  48.             if (dist[v] > dist[u] + w)
  49.             {
  50.                 dist[v] = dist[u] + w;
  51.                 fila.push({dist[v], v});
  52.             }
  53.         }
  54.     }
  55.  
  56.     ll resp = INF;
  57.     for (int i = 1; i <= idx; i++)
  58.     {
  59.         auto[a, b, c] = arr[i];
  60.         if (a == x || b == x || c == x) resp = min(resp, dist[i]);
  61.     }
  62.  
  63.     return resp;
  64. }
  65.  
  66. void build(int a, int b, int c)
  67. {
  68.     idx = 0;
  69.     queue<tuple<int, int, int> > fila;
  70.     fila.push({0, 0, c});
  71.     vis[0][0][c] = ++idx;
  72.     while (!fila.empty())
  73.     {
  74.         auto[a1, a2, a3] = fila.front();
  75.         int x = vis[a1][a2][a3]; fila.pop();
  76.         int p = min(a1, b-a2); // 1 - 2
  77.         arr[x] = {a1, a2, a3};
  78.         if (!vis[a1-p][a2+p][a3])
  79.         {
  80.             vis[a1-p][a2+p][a3] = ++idx;
  81.             fila.push({a1-p, a2+p, a3});
  82.         }
  83.         grafo[x].push_back({vis[a1-p][a2+p][a3], p});
  84.         p = min(a1, c-a3); // 1 - 3
  85.         if (!vis[a1-p][a2][a3+p])
  86.         {
  87.             vis[a1-p][a2][a3+p] = ++idx;
  88.             fila.push({a1-p, a2, a3+p});
  89.         }
  90.         grafo[x].push_back({vis[a1-p][a2][a3+p], p});
  91.         p = min(a2, a-a1); // 2 - 1
  92.         if (!vis[a1+p][a2-p][a3])
  93.         {
  94.             vis[a1+p][a2-p][a3] = ++idx;
  95.             fila.push({a1+p, a2-p, a3});
  96.         }
  97.         grafo[x].push_back({vis[a1+p][a2-p][a3], p});
  98.         p = min(a3, a-a1); // 3 - 1
  99.         if (!vis[a1+p][a2][a3-p])
  100.         {
  101.             vis[a1+p][a2][a3-p] = ++idx;
  102.             fila.push({a1+p, a2, a3-p});
  103.         }
  104.         grafo[x].push_back({vis[a1+p][a2][a3-p], p});
  105.         p = min(a2, c-a3); // 2 - 3
  106.         if (!vis[a1][a2-p][a3+p])
  107.         {
  108.             vis[a1][a2-p][a3+p] = ++idx;
  109.             fila.push({a1, a2-p, a3+p});
  110.         }
  111.         grafo[x].push_back({vis[a1][a2-p][a3+p], p});
  112.         p = min(a3, b-a2); // 3 - 2
  113.         if (!vis[a1][a2+p][a3-p])
  114.         {
  115.             vis[a1][a2+p][a3-p] = ++idx;
  116.             fila.push({a1, a2+p, a3-p});
  117.         }
  118.         grafo[x].push_back({vis[a1][a2+p][a3-p], p});
  119.     }
  120. }
  121.  
  122. int main()
  123. {_
  124.     cin >> t;
  125.     while (t--)
  126.     {
  127.         cin >> a >> b >> c >> d;
  128.         build(a, b, c);
  129.         for (int i = d; i >= 0; i--)
  130.         {
  131.             if (dijkstra(i) != INF)
  132.             {
  133.                 cout << dijkstra(i) << ' ' << i << endl;
  134.                 break;
  135.             }
  136.         }
  137.        
  138.         for (int i = 1; i <= idx; i++)
  139.             grafo[i].clear();
  140.     }  
  141. }
  142.  
  143.  
  144.  
  145.  
  146.  
  147.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement