這道題目不能說什麼了，狂改了很久很久，現在終於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
