#include <bits/stdc++.h> using namespace std; map<pair<pair<int, int>, int>, int> memo; int n; int res[1000006]; int T[3]; int t[3]; int main() { for (int i = 0; i < 3; ++i) { scanf("%d", &T[i]); } for(int i = 0; i <= T[2]; ++i) { res[i] = 1000000000; } for (int i = 0; i < 3; ++i) { scanf("%d", &t[i]); } queue<pair<pair<int, int>, int>> q; q.push({{t[0], t[1]}, t[2]}); memo[{{t[0], t[1]}, t[2]}] = 1; for (int i = 0; i < 3; ++i) { res[t[i]] = 1; } while (!q.empty()) { auto w = q.front(); q.pop(); // printf("%d %d %d %d\n", w.first.first, w.first.second, w.second, memo[w]); res[w.first.first] = min(res[w.first.first], memo[w]); res[w.first.second] = min(res[w.first.second], memo[w]); res[w.second] = min(res[w.second], memo[w]); for (int i = 0; i <= 2; ++i) { for (int j = 0; j <= 2; ++j) { if (i == j) { continue; } t[0] = w.first.first; t[1] = w.first.second; t[2] = w.second; // z i do j if (t[i] + t[j] <= T[j]) { t[j] = t[i] + t[j]; t[i] = 0; } else { t[i] = t[i] - (T[j] - t[j]); t[j] = T[j]; } pair<pair<int, int>, int> c = {{t[0], t[1]}, t[2]}; if (memo[c] != 0) { continue; } memo[c] = memo[w] + 1; q.push(c); } } } for (int i = 0; i <= T[2]; ++i) { printf("%d ", (res[i] == 1000000000 ? -1 : res[i] - 1)); } }
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 | #include <bits/stdc++.h> using namespace std; map<pair<pair<int, int>, int>, int> memo; int n; int res[1000006]; int T[3]; int t[3]; int main() { for (int i = 0; i < 3; ++i) { scanf("%d", &T[i]); } for(int i = 0; i <= T[2]; ++i) { res[i] = 1000000000; } for (int i = 0; i < 3; ++i) { scanf("%d", &t[i]); } queue<pair<pair<int, int>, int>> q; q.push({{t[0], t[1]}, t[2]}); memo[{{t[0], t[1]}, t[2]}] = 1; for (int i = 0; i < 3; ++i) { res[t[i]] = 1; } while (!q.empty()) { auto w = q.front(); q.pop(); // printf("%d %d %d %d\n", w.first.first, w.first.second, w.second, memo[w]); res[w.first.first] = min(res[w.first.first], memo[w]); res[w.first.second] = min(res[w.first.second], memo[w]); res[w.second] = min(res[w.second], memo[w]); for (int i = 0; i <= 2; ++i) { for (int j = 0; j <= 2; ++j) { if (i == j) { continue; } t[0] = w.first.first; t[1] = w.first.second; t[2] = w.second; // z i do j if (t[i] + t[j] <= T[j]) { t[j] = t[i] + t[j]; t[i] = 0; } else { t[i] = t[i] - (T[j] - t[j]); t[j] = T[j]; } pair<pair<int, int>, int> c = {{t[0], t[1]}, t[2]}; if (memo[c] != 0) { continue; } memo[c] = memo[w] + 1; q.push(c); } } } for (int i = 0; i <= T[2]; ++i) { printf("%d ", (res[i] == 1000000000 ? -1 : res[i] - 1)); } } |