学步园

http://poj.org/problem?id=2545

求Hi(p1,p2,p3), 用bfs搜索即可。用优先队列做，每次让最小的出队，同时衍生出3种新的情况，map判重，出队i次，ok。

#include <stdio.h>
#include <queue>
#include <map>
using namespace std;
struct NODE{
    int a,b,c;
    __int64 k;
    void init(int _a=0,int _b=0,int _c=0,__int64 _k=0){
        a=_a,b=_b,c=_c,k=_k;
    }
/*    friend bool operator < (const NODE &x, const NODE &y){
        return (x.k<y.k);
    }*/
    friend bool operator > (const NODE &x, const NODE &y){
        return (x.k>y.k);
    }
};
int main(){
    int p1,p2,p3,i,n,k;
    NODE x1,x2,x3,tmp,tmp1,tmp2,tmp3;
    scanf("%d%d%d%d",&p1,&p2,&p3,&n);
    x1.init(1,0,0,p1);
    x2.init(0,1,0,p2);
    x3.init(0,0,1,p3);
    priority_queue < NODE , vector <NODE> , greater<NODE> > q;
    map <__int64,int> h;
    map <__int64,int>::iterator it;
    k=0;
    q.push(x1),q.push(x2),q.push(x3);
    tmp=q.top();
    h[p1]=1;h[p2]=1;h[p3]=1;
    for (k=1;k<=n;k++)
    {
        tmp1=tmp2=tmp3=tmp=q.top();
//        printf("node = %lld\n",tmp1.k);
        q.pop();
        tmp1.a++;tmp1.k=tmp1.k*p1;
        tmp2.b++;tmp2.k=tmp2.k*p2;
        tmp3.c++;tmp3.k=tmp3.k*p3;
        it=h.find(tmp1.k);
        if (it==h.end()){
            h[tmp1.k]=1;
            q.push(tmp1);
        }

        it=h.find(tmp2.k);
        if (it==h.end()){
            h[tmp2.k]=1;
            q.push(tmp2);
        }

        it=h.find(tmp3.k);
        if (it==h.end()){
            h[tmp3.k]=1;
            q.push(tmp3);
        }
    }
    printf("%lld\n",tmp.k);

    return 0;
}