#include <bits/stdc++.h> using namespace std; typedef long long lld; // const int DEPTH = 50; lld mp(const int &a, const int &b) { return ((lld)a << 32) + (lld)b; } int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int A, B, C, a, b, c; cin >> A >> B >> C; cin >> a >> b >> c; vector<int> dist(C + 1, -1); dist[a] = dist[b] = dist[c] = 0; queue<pair<lld, int>> q; q.push(make_pair(mp(a, b), 0)); unordered_map<lld, bool> visited; visited[q.front().first] = true; while (!q.empty()) { // if (q.front().second > DEPTH) { // q.pop(); // continue; // } int x = (q.front().first >> 32), y = (q.front().first & 0xFFFFFFFF); int z = a + b + c - x - y, d = q.front().second; q.pop(); if (dist[x] < 0 || dist[x] > d) dist[x] = d; if (dist[y] < 0 || dist[y] > d) dist[y] = d; if (dist[z] < 0 || dist[z] > d) dist[z] = d; lld next = mp(min(A, x + y), max(0, x + y - A)); if (!visited.count(next)) { visited[next] = true; q.push(make_pair(next, d + 1)); } next = mp(min(A, x + z), y); if (!visited.count(next)) { visited[next] = true; q.push(make_pair(next, d + 1)); } next = mp(max(0, x + y - B), min(B, x + y)); if (!visited.count(next)) { visited[next] = true; q.push(make_pair(next, d + 1)); } next = mp(max(0, x + z - C), y); if (!visited.count(next)) { visited[next] = true; q.push(make_pair(next, d + 1)); } next = mp(x, min(B, y + z)); if (!visited.count(next)) { visited[next] = true; q.push(make_pair(next, d + 1)); } next = mp(x, max(0, y + z - C)); if (!visited.count(next)) { visited[next] = true; q.push(make_pair(next, d + 1)); } } for (int &i : dist) cout << i << ' '; cout << '\n'; }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 | #include <bits/stdc++.h> using namespace std; typedef long long lld; // const int DEPTH = 50; lld mp(const int &a, const int &b) { return ((lld)a << 32) + (lld)b; } int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int A, B, C, a, b, c; cin >> A >> B >> C; cin >> a >> b >> c; vector<int> dist(C + 1, -1); dist[a] = dist[b] = dist[c] = 0; queue<pair<lld, int>> q; q.push(make_pair(mp(a, b), 0)); unordered_map<lld, bool> visited; visited[q.front().first] = true; while (!q.empty()) { // if (q.front().second > DEPTH) { // q.pop(); // continue; // } int x = (q.front().first >> 32), y = (q.front().first & 0xFFFFFFFF); int z = a + b + c - x - y, d = q.front().second; q.pop(); if (dist[x] < 0 || dist[x] > d) dist[x] = d; if (dist[y] < 0 || dist[y] > d) dist[y] = d; if (dist[z] < 0 || dist[z] > d) dist[z] = d; lld next = mp(min(A, x + y), max(0, x + y - A)); if (!visited.count(next)) { visited[next] = true; q.push(make_pair(next, d + 1)); } next = mp(min(A, x + z), y); if (!visited.count(next)) { visited[next] = true; q.push(make_pair(next, d + 1)); } next = mp(max(0, x + y - B), min(B, x + y)); if (!visited.count(next)) { visited[next] = true; q.push(make_pair(next, d + 1)); } next = mp(max(0, x + z - C), y); if (!visited.count(next)) { visited[next] = true; q.push(make_pair(next, d + 1)); } next = mp(x, min(B, y + z)); if (!visited.count(next)) { visited[next] = true; q.push(make_pair(next, d + 1)); } next = mp(x, max(0, y + z - C)); if (!visited.count(next)) { visited[next] = true; q.push(make_pair(next, d + 1)); } } for (int &i : dist) cout << i << ' '; cout << '\n'; } |