#include <cstdio> #include <queue> #include <algorithm> using namespace std; struct request{ int aa; int bb; int tt; }; int main() { int A, B, C, a, b, c; queue<request> todo; scanf("%d %d %d %d %d %d", &A, &B, &C, &a, &b, &c); int sum = a + b + c; int D[A+1][B+1]; for (int i=0;i<=A;i++) for (int j=0;j<=B;j++) D[i][j] = -1; int R[C+1]; for (int i=0;i<=C;i++) R[i] = -1; todo.push(request{a,b,0}); while (!todo.empty()) { //request r = todo.front(); a = todo.front().aa; b = todo.front().bb; c = sum - a - b; int t = todo.front().tt; todo.pop(); if (R[a] == -1) R[a] = t; if (R[b] == -1) R[b] = t; if (R[c] == -1) R[c] = t; // A->C int tmp2, tmp = max(0,sum-C-b); if (D[tmp][b] == -1) {D[tmp][b] = -2; todo.push(request{tmp,b,t+1});} // B->C tmp = max(0,sum-C-a); if (D[a][tmp] == -1) {D[a][tmp] = -2; todo.push(request{a,tmp,t+1});} // A->B tmp = max(0,a+b-B); tmp2 = min(B,a+b); if (D[tmp][tmp2] == -1) {D[tmp][tmp2] = -2; todo.push(request{tmp,tmp2,t+1});} // B->A tmp = min(A,a+b); tmp2 = max(0,b+a-A); if (D[tmp][tmp2] == -1) {D[tmp][tmp2] = -2; todo.push(request{tmp,tmp2,t+1});} // C->A tmp = min(A,sum-b); if (D[tmp][b] == -1) {D[tmp][b] = -2; todo.push(request{tmp,b,t+1});} // B->C tmp = min(B,sum-a); if (D[a][tmp] == -1) {D[a][tmp] = -2; todo.push(request{a,tmp,t+1});} } for (int i=0;i<=C;i++) printf("%d ", R[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 | #include <cstdio> #include <queue> #include <algorithm> using namespace std; struct request{ int aa; int bb; int tt; }; int main() { int A, B, C, a, b, c; queue<request> todo; scanf("%d %d %d %d %d %d", &A, &B, &C, &a, &b, &c); int sum = a + b + c; int D[A+1][B+1]; for (int i=0;i<=A;i++) for (int j=0;j<=B;j++) D[i][j] = -1; int R[C+1]; for (int i=0;i<=C;i++) R[i] = -1; todo.push(request{a,b,0}); while (!todo.empty()) { //request r = todo.front(); a = todo.front().aa; b = todo.front().bb; c = sum - a - b; int t = todo.front().tt; todo.pop(); if (R[a] == -1) R[a] = t; if (R[b] == -1) R[b] = t; if (R[c] == -1) R[c] = t; // A->C int tmp2, tmp = max(0,sum-C-b); if (D[tmp][b] == -1) {D[tmp][b] = -2; todo.push(request{tmp,b,t+1});} // B->C tmp = max(0,sum-C-a); if (D[a][tmp] == -1) {D[a][tmp] = -2; todo.push(request{a,tmp,t+1});} // A->B tmp = max(0,a+b-B); tmp2 = min(B,a+b); if (D[tmp][tmp2] == -1) {D[tmp][tmp2] = -2; todo.push(request{tmp,tmp2,t+1});} // B->A tmp = min(A,a+b); tmp2 = max(0,b+a-A); if (D[tmp][tmp2] == -1) {D[tmp][tmp2] = -2; todo.push(request{tmp,tmp2,t+1});} // C->A tmp = min(A,sum-b); if (D[tmp][b] == -1) {D[tmp][b] = -2; todo.push(request{tmp,b,t+1});} // B->C tmp = min(B,sum-a); if (D[a][tmp] == -1) {D[a][tmp] = -2; todo.push(request{a,tmp,t+1});} } for (int i=0;i<=C;i++) printf("%d ", R[i]); } |