GitHub - jzplp/aoapc-UVA-Answer: 算法竞赛入门经典 例题和习题答案 刘汝佳 第二版
使用广度优先搜索和优先队列,如果找到最小的点则退出。找不到就遍历所有的情况。
#include<stdio.h>
#include<queue>
using namespace std;
struct Node {
int v[3];
int dist;
bool operator < (const Node &r) const {
return dist > r.dist;
}
};
int vis[202][202];
int dist[202];
int volume[3], d;
bool judge(Node * no) {
for(int i = 0; i < 3; ++i) {
if(no->v[i] == d) return true;
}
return false;
}
void handleOne(Node * no) {
for(int i = 0; i < 3; ++i) {
if(dist[no->v[i]] == -1 || dist[no->v[i]] > no->dist) dist[no->v[i]] = no->dist;
}
}
bool getNextNode(Node * no, int i, int j, Node * no2) {
int k;
if(no->v[i] == 0 || i == j || no->v[j] == volume[j])
return false;
int jLen = volume[j] - no->v[j];
int minLen = jLen > no->v[i] ? no->v[i] : jLen;
for(k = 0; k < 3; ++k) {
no2->v[k] = no->v[k];
}
no2->dist = no->dist + minLen;
no2->v[i] -= minLen;
no2->v[j] += minLen;
return true;
}
void compute() {
Node no, no2;
int i, j, k;
priority_queue<Node> pq;
no.v[0] = 0; no.v[1] = 0; no.v[2] = volume[2]; no.dist = 0;
pq.push(no);
while(!pq.empty()) {
no = pq.top();
pq.pop();
handleOne(&no);
if(judge(&no)) return;
for(i = 0; i < 3; ++i) {
for(j = 0; j < 3; ++j) {
if(!getNextNode(&no, i, j, &no2)) continue;
if(vis[no2.v[0]][no2.v[1]]) continue;
vis[no2.v[0]][no2.v[1]] = 1;
pq.push(no2);
}
}
}
}
void init() {
for(int i = 0; i < 202; ++i) {
dist[i] = -1;
for(int j = 0; j < 202; ++j) {
vis[i][j] = 0;
}
}
}
int main() {
int t;
scanf("%d", &t);
while(t--) {
scanf("%d %d %d %d", &volume[0], &volume[1], &volume[2], &d);
init();
compute();
while(d >= 0) {
if(dist[d] != -1) {
printf("%d %d\n", dist[d], d);
break;
}
--d;
}
}
return 0;
}