#include <bits/stdc++.h> #define qio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0) #define debug(x) cerr<<#x<<" "<<x<<endl #define ll long long #define st first #define nd second using namespace std; int n, t, dp[100005], lim[5], val[5], num; queue <pair<pair<pair<int, int>, int>, int>> Q; pair<pair<int, int>, int> p; map<pair<pair<int, int>, int>, int> M; void dodaj(int a, int b, int c) { int temp = 0; int ile = 0; //1 2 temp = lim[2] - b; ile = min(temp, a); Q.push({ {{a - ile,b + ile},c},num + 1 }); //2 3 temp = lim[3] - c; ile = min(temp, b); Q.push({ {{a,b - ile},c + ile},num + 1 }); //1 3 temp = lim[3] - c; ile = min(temp, a); Q.push({ {{a - ile,b},c + ile},num + 1 }); //2 1 temp = lim[1] - a; ile = min(temp, b); Q.push({ {{a + ile,b - ile},c},num + 1 }); //3 2 temp = lim[2] - b; ile = min(temp, c); Q.push({ {{a,b + ile},c - ile},num + 1 }); //3 1 temp = lim[1] - a; ile = min(temp, c); Q.push({ {{a + ile,b},c - ile},num + 1 }); } int main() { qio; cin >> lim[1] >> lim[2] >> lim[3]; cin >> val[1] >> val[2] >> val[3]; Q.push({ {{val[1],val[2]},val[3]},0 }); for (int i = 0; i <= lim[3]; i++) { dp[i] = INT_MAX; } while (!Q.empty()) { p = Q.front().st; val[1] = Q.front().st.st.st; val[2] = Q.front().st.st.nd; val[3] = Q.front().st.nd; num = Q.front().nd; //cout << val[1] << " " << val[2] << " " << val[3] << " " << num << endl; Q.pop(); if (M[p] == 0) { M[p] = 1; dp[val[1]] = min(dp[val[1]], num); dp[val[2]] = min(dp[val[2]], num); dp[val[3]] = min(dp[val[3]], num); dodaj(val[1], val[2], val[3]); } } for (int i = 0; i <= lim[3]; i++) { if (dp[i] == INT_MAX) cout << -1 << " "; else cout << dp[i] << " "; } }
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 | #include <bits/stdc++.h> #define qio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0) #define debug(x) cerr<<#x<<" "<<x<<endl #define ll long long #define st first #define nd second using namespace std; int n, t, dp[100005], lim[5], val[5], num; queue <pair<pair<pair<int, int>, int>, int>> Q; pair<pair<int, int>, int> p; map<pair<pair<int, int>, int>, int> M; void dodaj(int a, int b, int c) { int temp = 0; int ile = 0; //1 2 temp = lim[2] - b; ile = min(temp, a); Q.push({ {{a - ile,b + ile},c},num + 1 }); //2 3 temp = lim[3] - c; ile = min(temp, b); Q.push({ {{a,b - ile},c + ile},num + 1 }); //1 3 temp = lim[3] - c; ile = min(temp, a); Q.push({ {{a - ile,b},c + ile},num + 1 }); //2 1 temp = lim[1] - a; ile = min(temp, b); Q.push({ {{a + ile,b - ile},c},num + 1 }); //3 2 temp = lim[2] - b; ile = min(temp, c); Q.push({ {{a,b + ile},c - ile},num + 1 }); //3 1 temp = lim[1] - a; ile = min(temp, c); Q.push({ {{a + ile,b},c - ile},num + 1 }); } int main() { qio; cin >> lim[1] >> lim[2] >> lim[3]; cin >> val[1] >> val[2] >> val[3]; Q.push({ {{val[1],val[2]},val[3]},0 }); for (int i = 0; i <= lim[3]; i++) { dp[i] = INT_MAX; } while (!Q.empty()) { p = Q.front().st; val[1] = Q.front().st.st.st; val[2] = Q.front().st.st.nd; val[3] = Q.front().st.nd; num = Q.front().nd; //cout << val[1] << " " << val[2] << " " << val[3] << " " << num << endl; Q.pop(); if (M[p] == 0) { M[p] = 1; dp[val[1]] = min(dp[val[1]], num); dp[val[2]] = min(dp[val[2]], num); dp[val[3]] = min(dp[val[3]], num); dodaj(val[1], val[2], val[3]); } } for (int i = 0; i <= lim[3]; i++) { if (dp[i] == INT_MAX) cout << -1 << " "; else cout << dp[i] << " "; } } |