UVA - 10603 Fill(bfs+ 우선 순위 큐 + 동적 계획)

FILL
There are three jugs with a volume of a, b and c liters. (a, b, and c are positive integers not greater than 200). The first and the second jug are initially empty, while the third
is completely filled with water. It is allowed to pour water from one jug into another until either the first one is empty or the second one is full. This operation can be performed zero, one or more times.
 
You are to write a program that computes the least total amount of water that needs to be poured; so that at least one of the jugs contains exactly d liters of water (d is a positive integer not greater than 200). If it is not possible to measure d liters this way your program should find a smaller amount of water d' < d which is closest to d and for which d' liters could be produced. When d' is found, your program should compute the least total amount of poured water needed to produce d' liters in at least one of the jugs.
 
Input
The first line of input contains the number of test cases. In the next T lines, T test cases follow. Each test case is given in one line of input containing four space separated integers - a, b, c and d.
 
Output
The output consists of two integers separated by a single space. The first integer equals the least total amount (the sum of all waters you pour from one jug to another) of poured water. The second integer equals d, if d liters of water could be produced by such transformations, or equals the closest smaller value d' that your program has found.
 
Sample Input
Sample Output
2 2 3 4 2 96 97 199 62
2 2 9859 62
 
제목의 뜻: 세 개의 컵의 용량은 각각 a, b, c로 처음에는 세 번째 컵에만 c리터의 물을 가득 채웠고 다른 두 개의 컵은 비어 있었다.최소한 몇 리터의 물을 부어야만 어떤 컵의 물을 d리터로 만들 수 있습니까?
만약 d리터를 맞추지 못한다면, 어떤 컵의 물을 가능한 한 d에 가깝게 해라.
해석: UVA 위의 데이터가 바뀌었을 수도 있어요. 저는 인터넷에 있는 다른 코드가 TLE인 것을 봤습니다. 그래서 이 문제를 단순한 bfs로 하면 시간이 초과될 수 있습니다. 그래서 저는 동태적인 기획 사상을 사용했습니다. ans수조로 모든 물을 저장하고 최소한 총 수량을 많이 써야 도착할 수 있으며 우선 대기열로 최적화할 수 있습니다.
즉, 매번 가장 적은 용수량의 노드를 추출하여 가장 적은 용수량의 노드 중 한 컵의 물의 용수량을 ans수조에 저장하고 계속 업데이트한다.마지막으로 d~0에서 첫 번째 용수량이 -1이 아닌 ans의 값을 출력합니다.
AC 코드:

#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>
using namespace std;

struct Node {
	int v[3],dist;
	bool operator < (const Node& rhs) const {
		return this->dist > rhs.dist; //      
	}
};
const int MAX = 200 + 5;
int vis[MAX][MAX],jug[3],ans[MAX];
int d;

void update(const Node& u) {
	for(int i = 0; i < 3; i++) {
		int t = u.v[i];
		if(ans[t] < 0 || u.dist < ans[t]) { //   t  ，       
			ans[t] = u.dist;
		}
	}
}

void bfs() {
	memset(vis,0,sizeof(vis));
	memset(ans,-1,sizeof(ans));
	
	priority_queue<Node> q; //      
	
	Node start;
	start.dist = 0;
	start.v[0] = 0;
	start.v[1] = 0;
	start.v[2] = jug[2];
	q.push(start);
	vis[0][0] = 1; //   vis
	while(!q.empty()) {
		Node u = q.top();
		q.pop();
		update(u);
		if(ans[d] >= 0) { //         >= 0，   
			break;
		}
		for(int i = 0; i < 3; i++) {
			for(int j = 0; j < 3; j++) {
				if(i == j) { //       
					continue;
				}
				if(!u.v[i] || u.v[j] == jug[j]) { //i   ，  j    ，  
					continue;
				}
				int amount = min(u.v[i],jug[j]-u.v[j]);
				Node u2 = u;
				u2.dist += amount;
				u2.v[i] -= amount;
				u2.v[j] += amount;
				if(!vis[u2.v[0]][u2.v[1]]) {
					vis[u2.v[0]][u2.v[1]] = true;
					q.push(u2);
				}
			}
		}
	}
	
}
int main() {
	int t;
	while(scanf("%d",&t) != EOF) {
		while(t--) {
			scanf("%d%d%d%d",&jug[0],&jug[1],&jug[2],&d);
			bfs();
			while(d >= 0) {
				if(ans[d] >= 0) {
					printf("%d %d
",ans[d],d);
					break;
				}
				d--;
			}
		}
	}
	return 0;
}