範例程式碼 uva10603

//uva10603
#include<iostream>
#include<queue>
#include<cstdio>
#include<algorithm>
#include<limits.h>
using namespace std;
int A, B, C, D;
int water[201][201], ans[201];
queue<int> queuea, queueb, queuec, queuetotal;

void pushnode(int a, int b, int c, int total){
    queuea.push(a), queueb.push(b), queuec.push(c), queuetotal.push(total);
}

void update(int a, int b, int c, int total){
    if (total >= ans[D]) return;
    if (total >= water[a][b]) return;
    water[a][b] = total;
    ans[a] = min(ans[a], total);
    ans[b] = min(ans[b], total);
    ans[c] = min(ans[c], total);
    if (a <= C - c)
        pushnode(0, b, c+a, total+a);
    else
        pushnode(a-C+c, b, C, total+C-c);
    if (a <= B - b)
        pushnode(0, b+a, c, total+a);
    else
        pushnode(a-B+b, B, c, total+B-b);
    if (b <= C - c)
        pushnode(a, 0, c+b, total+b);
    else
        pushnode(a, b-C+c, C, total+C-c);
    if (b <= A - a)
        pushnode(a+b, 0, c, total+b);
    else
        pushnode(A, b-A+a, c, total+A-a);
    if (c <= A - a)
        pushnode(a+c, b, 0, total+c);
    else
        pushnode(A, b, c-A+a, total+A-a);
    if (c <= B - b)
        pushnode(a, b+c, 0, total+c);
    else
        pushnode(a, B, c-B+b, total+B-b);
}

void bfs(int a, int b, int c, int total){
    pushnode(a, b, c, total);
    while (!queuea.empty()){
        a = queuea.front(),queuea.pop();
        b = queueb.front(),queueb.pop();
        c = queuec.front(),queuec.pop();
        total = queuetotal.front(),queuetotal.pop();
        update(a, b, c, total);
    }
}

main(){
    int n, i, j, k;

    scanf("%d",&n);
    while (n--){
            scanf("%d%d%d%d", &A, &B, &C, &D);
            for (i = 0; i <= A; i++)
                for (j = 0; j <= B; j++)
                    water[i][j] = INT_MAX;
            for (i = 0; i <= D; i++)
                ans[i] = INT_MAX;
            bfs(0, 0, C, 0);
            for (i = D; ans[i] == INT_MAX ; i--);
            printf("%d %d\n", ans[i], i);
    }
    return 0;
}