用了递归，递归里面有约束，保证约束条件。
#include<iostream>
using namespace std;
int M;
int N;
int matrix[100][100];
int Level[100];
int maximum=999999999;
int GetMinimun(int i,int rangeMin,int rangeMax);
int fmin(int x,int y);
int fmax(int x,int y);
int main()
{
	while(cin>>M>>N)
	{
		for(int i=0;i<N;i++)
			for(int j=0;j<N;j++)
				matrix[i][j]=maximum;
		bool first=true;
		int min=0;
		int max=0;
		int L;//等级
		int X;//替代品个数
		for(int i=0;i<N;i++)
		{
			cin>>matrix[i][i];//输入价格P
			cin>>L;//输入等级
			Level[i]=L;
			cin>>X;//输入替代品个数
			if(first)
			{
				first = false;

				min=L-M;
				
				max=L+M;
			}
			if(L>=min && L<=max)
			{
				//确定该路径的范围
				//ranges[i].min=fmax(min,L-M);

				//ranges[i].max=fmin(max,L+M);

				for(int j=0;j<X;j++)
				{
					int T;

					cin>>T;

					cin>>matrix[i][T-1];
				}
			}
			else
			{
				for(int j=0;j<X;j++)
				{
					int T1,T2;
					cin>>T1>>T2;
				}
			}
		}
		cout<<GetMinimun(0,min,max);
	}
}
int GetMinimun(int i,int rangeMin,int rangeMax)
{

	int result=matrix[i][i];

	for(int j=i+1;j<N;j++)
	{
		if(matrix[i][j]!=maximum && Level[j]>=rangeMin && Level[j]<=rangeMax && j!=i)//可以交换的物品
		{
			int re=0;

			re=GetMinimun(j,fmax(rangeMin,Level[j]-M),fmin(rangeMax,Level[j]+M))+matrix[i][j];

			if(result>re)
				result=re;
		}
	}
	return result;
}
int fmin(int x,int y)
{
	return x<y?x:y;
}
int fmax(int x,int y)
{
	return x>y?x:y;
}

• Re:最关键的是图的表示+图的遍历，没用最短路径，直接遍历0MS (5) huangkaike 2012-07-15 19:29:03
• 我也觉得是dfs暴力搜索，然后加上一些剪枝优化即可，0MS (2739) hujk2008 2012-09-15 01:00:36