枚举可能的rank 
#include<stdio.h>
#include<memory.h>
int main(){
	int m,n,s[150][150],l[150],dis[150],max_rank=0;
	int best;
	bool visited[150]={false};
	memset(s,-1,sizeof(s));
	scanf("%d%d",&m,&n);
	for(int i=1;i<=n;i++){
		int num;
		scanf("%d%d%d",s[0]+i,l+i,&num);
		if(l[i]>max_rank)
			max_rank=l[i];
		for(int j=0;j<num;j++){
			int tem;
			scanf("%d",&tem);
			scanf("%d",&s[tem][i]);
		}
	}
	l[0]=l[1],best=s[0][1];
	if(max_rank-l[0]>m)
		max_rank=m+l[0];
	while(max_rank>=l[0]){
		memset(visited,false,sizeof(visited));
		for(int i=1;i<=n;i++)
			dis[i]=s[0][i];
		for(int i=1;i<=n;i++){
			int j=1;
			while(j<=n&&(visited[j]||l[i]>max_rank||max_rank-m>l[i]))
				j++;
			if(j==n+1)
				break;
			for(int k=j+1;k<=n;k++)
				if(!visited[k]&&dis[k]<dis[j]&&l[k]<=max_rank&&l[k]>=max_rank-m)
					j=k;
			visited[j]=true;
			for(int k=1;k<=n;k++)
				if(!visited[k]&&s[j][k]!=-1&&s[j][k]+dis[j]<dis[k]&&l[k]<=max_rank&&l[k]>=max_rank-m)
					dis[k]=dis[j]+s[j][k];
		}
		if(dis[1]<best)
			best=dis[1];
		max_rank--;
	}
	printf("%d\n",best);
	return 0;
}

• Re:一直wa 帮忙看看吧 (1204) hansechang 2008-08-02 09:20:15