程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> POJ 2420 A Star not a Tree? (模擬退火)

POJ 2420 A Star not a Tree? (模擬退火)

編輯：C++入門知識

POJ 2420 A Star not a Tree? (模擬退火)

題目地址：POJ 2420

今天在比賽遇到了這題。。於是現場學了一下模擬退火。。。。

這題是先初始化為一個點，然後不斷趨近距離和最短的點。還是挺簡單的。。

代碼如下：

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 

using namespace std;
#define LL __int64
const int INF=0x3f3f3f3f;
int n;
struct point
{
    int x, y;
}dian[200];
double dist(point a, point b)
{
    return sqrt((a.x-b.x)*(a.x-b.x)*1.0+(a.y-b.y)*(a.y-b.y));
}
double juhe(point x)
{
    int i;
    double z=0;
    for(i=0;i0.2)
    {
        flag=1;
        while(flag)
        {
            flag=0;
            point now;
            now.x=st.x+step;
            now.y=st.y;
            s=juhe(now);
            if(d>s)
            {
                flag=1;
                d=s;
                ed=now;
            }
            now.x=st.x-step;
            now.y=st.y;
            s=juhe(now);
            if(d>s)
            {
                flag=1;
                d=s;
                ed=now;
            }
            now.x=st.x;
            now.y=st.y+step;
            s=juhe(now);
            if(d>s)
            {
                flag=1;
                d=s;
                ed=now;
            }
            now.x=st.x;
            now.y=st.y-step;
            s=juhe(now);
            if(d>s)
            {
                flag=1;
                d=s;
                ed=now;
            }
            if(flag)
                st=ed;
        }
        step/=2.0;
    }
    printf("%.0f\n",d);
    return 0;
}