#include<stdio.h>
#include<string.h>
const int N=102,INF=1<<30;
int lim,n,ans,mmin;
int map[N][N],level[N],mark[N];
int abs(int t)
{
	return t>0?t:-t;
}
	
void dfs(int t,int money,int MIN,int MAX)
{
	if(money>map[0][1]||MAX-MIN>lim) return;
	if(t==1)
	{
		if(mmin>money)
			mmin=money;
		return ;
	}
    for(int i=1;i<=n;++i)
        if(mark[i]==0&&map[t][i]!=-1&&(map[0][t]+map[t][i]<map[0][i])&&abs(level[i]-MIN)<=lim&&abs(level[i]-MAX)<=lim)
		{
			mark[i]=1;
			int tmax=MAX,tmin=MIN;
			if(level[i]>MAX)
				MAX=level[i];
			else if(level[i]<MIN)
				MIN=level[i];
			dfs(i,money+map[t][i],MIN,MAX);
			mark[i]=0;
			MIN=tmin;
			MAX=tmax;
		}
}
int main()
{
	//freopen("d:\\1.txt","r",stdin);
    int i,j,v,l,m,no,subv;
    while(scanf("%d%d",&lim,&n)==2)
    {
        memset(map,-1,sizeof(map));
        for(i=1;i<=n;++i)
        {
            scanf("%d%d%d",&v,&l,&m);
            map[0][i]=v;
            level[i]=l;
            for(j=1;j<=m;++j)
            {
                scanf("%d%d",&no,&subv);
                map[no][i]=subv;
            }
        }
        int tmp;
        ans=-1;
        for(i=1;i<=n;++i)
        {
        	memset(mark,0,sizeof(mark));
        	mmin=INF;
        	mark[i]=1;
            dfs(i,map[0][i],level[i],level[i]);
            if(ans==-1||mmin<ans)
                ans=mmin;
        }
        printf("%d\n",ans);
    }
    return 0;
}

• Re:请问有什么需要特别注意？？？为什么一直不是超时就是WA (1584) yanhaitao 2011-12-17 20:54:46
• Re:请问有什么需要特别注意？？？为什么一直不是超时就是WA (12) yanhaitao 2011-12-17 20:55:24