Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <queue>
- #include <string>
- #include <algorithm>
- #include <vector>
- #include <cmath>
- #include <iomanip>
- #include <map>
- #include <cstring>
- #include <set>
- #include <stack>
- #include <bitset>
- #define ll long long
- #define INF (1e15)
- #define MAX (int) 100000
- #define MOD 1000000007
- #define par pair<int, ll>
- #define all(v) v.begin(), v.end()
- #define sz(x) (int) ((x).size())
- #define esq(x) (x<<1)
- #define dir(x) ((x<<1)|1)
- #define lsb(x) (x & -x)
- #define W(x) cout << #x << ": " << x << endl
- #define Wii(x) cout << x.first << ' ' << x.second << endl
- #define _ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
- using namespace std;
- int a, b, c, d, t, idx, vis[201][201][201];
- ll dist[MAX];
- vector<par> grafo[MAX];
- tuple<int, int, int> arr[MAX];
- ll dijkstra(int x)
- {
- priority_queue<par, vector<par>, greater<par> > fila;
- for (int i = 1; i <= idx; i++)
- dist[i] = INF;
- fila.push({0, vis[0][0][c]});
- dist[vis[0][0][c]] = 0;
- while (!fila.empty())
- {
- auto[d, u] = fila.top(); fila.pop();
- if (d != dist[u]) continue;
- for (auto[v, w] : grafo[u])
- {
- if (dist[v] > dist[u] + w)
- {
- dist[v] = dist[u] + w;
- fila.push({dist[v], v});
- }
- }
- }
- ll resp = INF;
- for (int i = 1; i <= idx; i++)
- {
- auto[a, b, c] = arr[i];
- if (a == x || b == x || c == x) resp = min(resp, dist[i]);
- }
- return resp;
- }
- void build(int a, int b, int c)
- {
- idx = 0;
- queue<tuple<int, int, int> > fila;
- fila.push({0, 0, c});
- vis[0][0][c] = ++idx;
- while (!fila.empty())
- {
- auto[a1, a2, a3] = fila.front();
- int x = vis[a1][a2][a3]; fila.pop();
- int p = min(a1, b-a2); // 1 - 2
- arr[x] = {a1, a2, a3};
- if (!vis[a1-p][a2+p][a3])
- {
- vis[a1-p][a2+p][a3] = ++idx;
- fila.push({a1-p, a2+p, a3});
- }
- grafo[x].push_back({vis[a1-p][a2+p][a3], p});
- p = min(a1, c-a3); // 1 - 3
- if (!vis[a1-p][a2][a3+p])
- {
- vis[a1-p][a2][a3+p] = ++idx;
- fila.push({a1-p, a2, a3+p});
- }
- grafo[x].push_back({vis[a1-p][a2][a3+p], p});
- p = min(a2, a-a1); // 2 - 1
- if (!vis[a1+p][a2-p][a3])
- {
- vis[a1+p][a2-p][a3] = ++idx;
- fila.push({a1+p, a2-p, a3});
- }
- grafo[x].push_back({vis[a1+p][a2-p][a3], p});
- p = min(a3, a-a1); // 3 - 1
- if (!vis[a1+p][a2][a3-p])
- {
- vis[a1+p][a2][a3-p] = ++idx;
- fila.push({a1+p, a2, a3-p});
- }
- grafo[x].push_back({vis[a1+p][a2][a3-p], p});
- p = min(a2, c-a3); // 2 - 3
- if (!vis[a1][a2-p][a3+p])
- {
- vis[a1][a2-p][a3+p] = ++idx;
- fila.push({a1, a2-p, a3+p});
- }
- grafo[x].push_back({vis[a1][a2-p][a3+p], p});
- p = min(a3, b-a2); // 3 - 2
- if (!vis[a1][a2+p][a3-p])
- {
- vis[a1][a2+p][a3-p] = ++idx;
- fila.push({a1, a2+p, a3-p});
- }
- grafo[x].push_back({vis[a1][a2+p][a3-p], p});
- }
- }
- int main()
- {_
- cin >> t;
- while (t--)
- {
- cin >> a >> b >> c >> d;
- build(a, b, c);
- for (int i = d; i >= 0; i--)
- {
- if (dijkstra(i) != INF)
- {
- cout << dijkstra(i) << ' ' << i << endl;
- break;
- }
- }
- for (int i = 1; i <= idx; i++)
- grafo[i].clear();
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement