#include <iostream>
#include <fstream>
#include <set>
#define  MAX_PRICE 10000000
using namespace std;

struct commodity
{
	int P,L;
	int N;
};
int minP[105]; //dijstra 算法的距离
int mat[105][105]; //邻接矩阵
int main()
{
	commodity c[105];//所有商品
	int M,N; 
	int i,p,l,x,j,No_,P_;
	//ifstream input;
	//input.open("data.txt",std::ios::in);
	
	while(cin>>M>>N)
	{
		memset(mat,0,sizeof(mat));
		memset(minP,0,sizeof(minP));
		//initialize
		for( i = 1; i <= N; i++)
		{
			for( j = 1; j <= N; j++)
			{
				if( i == j)
				{
					mat[i][j] = 0;
				}
				else
					mat[i][j] = MAX_PRICE;
			}
		}
		//先输入邻接关系
		for( i = 1; i<= N;i++)
		{
			cin>>p>>l>>x;
			minP[i] = p;
			c[i].P = p;
			c[i].N = x;
			c[i].L = l;

			for( j = 0; j < x; j++)
			{
				cin>>No_>>P_;
				mat[No_][i] = P_;
			}
		}
		//按照地位身份排除一些情况
		for( i = 1; i <= N; i++)
		{
			for( j = 1; j <= N; j++)
			{
				if(mat[i][j] != 0 && mat[i][j] != MAX_PRICE)
				{
					if( abs(c[i].L - c[j].L) >  M)
					{
						mat[i][j] = MAX_PRICE;
					}
				}
			}
		}
		//找到原点集合，就是那些没有前驱的点，有一个虚拟节点，这些点到虚拟节点的距离就是他们自己的价格
		std::set<int> minset,others;
		std::set<int>::iterator it,it_j;
		for( i = 1; i <= N; i++)
		{
			int inward = 0;
			for( j = 1; j <= N; j++)
			{
				if(i != j && mat[j][i] != MAX_PRICE)
				{
					inward++;
				}
			}
			if(inward == 0)
			{
				minset.insert(i);
			}
			else
				others.insert(i);
		}
		int dis,minDis;
		//如果最终的商品也没有前驱，那么只能用金币购买
		if(minset.find(1) != minset.end())
		{
			cout<<c[1].P<<endl;
		}
		else
		{
			//用dijstra算法，找出出虚拟节点到商品1的距离，初始距离不是最大，而是使用每个商品的金币价格
			while(1)
			{

				for( it = minset.begin(); it != minset.end(); ++it)
				{
					for( it_j = others.begin(); it_j !=others.end(); ++it_j)
					{
						if(*it != *it_j &&  mat[*it][*it_j] != MAX_PRICE)
							minP[*it_j] = min(minP[*it_j],minP[*it] + mat[*it][*it_j]);
					}
				}
				minDis = 1000000000;
				for( it_j = others.begin(); it_j != others.end() ; ++it_j)
				{
					if(minP[*it_j] < minDis)
					{
						minDis = minP[*it_j];
						it = it_j;
					}
				}
				if(*it == 1)
				{
					dis = minDis;
					break;
				}
				minset.insert(*it);
				others.erase(it);
			}
			cout<<dis<<endl;

		}

	}
	
	
	return 0;
	



}

• 大哥你算法有问题 (173) justryit 2013-07-31 09:56:19