K_程式人

https://uva.onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=1544

#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;

}