poj-1062-昂贵的聘礼

这道题目不能说什么了，狂改了很久很久，现在终于AC了，在这道题目上花的时间太多太多了，，，，
一开始看这道题目的时候想到的是用DFS，后来想起来前天看了A*算法。就用A*算法写了。
 [html] 
#include<stdio.h> 
#include<math.h> 
int map[301][301];//记录边 
int di[301],val[301];//记录地位，价值 
struct list 
{ 
    int a; 
    int max; 
    int min; 
    int v; 
}open[301],close[301],ex;//open是起始数组，close是结果数组 
int open_n=0; 
int close_n=0; 
int cheak[301][301]; 
int m,n; 
void guanlian() 
{ 
    int open_first,i,j,open_val,open_max,open_min; 
    open_first=open[open_n-1].a;//------------------------------------------------ 
    open_val=open[open_n-1].v; 
    open_max=open[open_n-1].max; 
    open_min=open[open_n-1].min;//    中间这部分是把open数组中价值最小的转移到close数组中 
    open_n--; 
    close[close_n]=open[open_n]; 
    close_n++;                 //------------------------------------------------- 
    for(i=1;i<=n;i++) 
    { 
        if(map[open_first][i]!=-1&&cheak[open_first][i]) 
        { 
            if((fabs(di[i]-open_max)<=m)&&fabs(di[i]-open_min)<=m) 
            { 
                if(di[i]<open_min)             //------------------------------------------- 
                { 
                    open[open_n].min=di[i]; 
                    open[open_n].max=open_max; 
                } 
                else if(di[i]>open_max)       //这部分是决定这条兑换链所涉及到的人的最大地位和最小地位 
                { 
                    open[open_n].max=di[i]; 
                    open[open_n].min=open_min; 
                } 
                else                           //---------------------------------------------- 
                {  
                    open[open_n].max=open_max; 
                    open[open_n].min=open_min; 
                } 
                cheak[open_first][i]=0; 
                open[open_n].a=i; 
                open[open_n].v=map[open_first][i]+open_val; 
                open_n++; 
            } 
        } 
    } 
    for(i=0;i<open_n;i++)//把open数组按照价值排序 
    { 
        for(j=i+1;j<open_n;j++) 
        { 
            if((open[i].v+val[open[i].a])<(open[j].v+val[open[j].a])) 
            { 
                ex=open[i];   
                open[i]=open[j]; 
                open[j]=ex; 
            } 
        } 
    } 
}    
int A() 
{ 
    int i,nmax,max; 
    open[0].a=1; 
    open[0].v=0; 
    open[0].max=di[1]; 
    open[0].min=di[1]; 
    open_n++; 
    while(open_n!=0) 
    { 
        guanlian(); 
    } 
    nmax=val[1]; 
    for(i=0;i<close_n;i++)//寻找close数组里面价值最小的值，即是结果值 
    { 
        max=close[i].v+val[close[i].a]; 
        if(max<nmax) 
        { 
            nmax=max; 
        } 
    } 
    return nmax; 
} 
int main() 
{ 
    int i,j,p,l,x,t,v,val_put; 
    for(i=1;i<=300;i++) 
    { 
        close[i].v=0; 
    } 
    for(i=1;i<=300;i++) 
    { 
        for(j=1;j<=300;j++) 
        { 
            cheak[i][j]=1; 
            map[i][j]=-1; 
        } 
    } 
    scanf("%d%d",&m,&n); 
    for(i=1;i<=n;i++) 
    { 
        scanf("%d%d%d",&p,&l,&x); 
        di[i]=l;val[i]=p; 
        for(j=1;j<=x;j++) 
        { 
            scanf("%d%d",&t,&v); 
            map[i][t]=v; 
        } 
    } 
    val_put=A(); 
    printf("%d/n",val_put); 
    return 0; 
} 
作者：rowanhaoa