#include<iostream>
using namespace std;
struct Nodes
{
	int weight;
	int dj;
};
Nodes node[100];//节点数组

int len;//节点个数
int w;//等级允许差距

int queue[100];//队列
int front=0,rear=0;

int min_cost=0x7fffffff;

//====邻接表========
struct Arcnode
{
	int data;//边的权值
	int adjvex;
	Arcnode *next;
};
typedef struct node
{
	Arcnode *first;
}nodes[100];
nodes bian;//边
//=====================

int result[100];//记录根节点的边的权值
int high;//访问过的最高等级
int low;//访问过的最低等级
int cost=0;//记录每次的花费

void dfs(int form)
{
	Arcnode *p=new(Arcnode);
	p=bian[form].first;//确定本次的起点

	int k=cost;//记住原始的cost值

	if(node[form].dj>high)high=node[form].dj;//更改访问过的等级
	if(node[form].dj<low)low=node[form].dj;//更改访问过的最低等级

	while(p)//只要有变继续递归
	{
		cost=k;//恢复原始值
		if(node[p->adjvex].dj-high>=-w&&node[p->adjvex].dj-low<=w)//
		{
			cost+=p->data+node[p->adjvex].weight-node[form].weight;
			if(min_cost>cost)min_cost=cost;//判断是否为最小值
			dfs(p->adjvex);
		}
		p=p->next;
	}
}

void BFS()
{
	int j,k;
	min_cost=node[0].weight;
	Arcnode *p=new(Arcnode);
	p=bian[0].first;
	while(p)
	{
		if((node[p->adjvex].dj-node[0].dj>=-w)&&(node[p->adjvex].dj-node[0].dj<=w))
		{
			queue[rear]=p->adjvex;
			result[rear++]=p->data;
		}
		p=p->next;
	}
	while(front!=rear)
	{
		j=queue[front];
		k=cost=result[front++]+node[j].weight;
		if(min_cost>cost)min_cost=cost;
		p=new(Arcnode);
		p=bian[j].first;
		while(p)
		{
			cost=k;
			if((node[p->adjvex].dj-high>=-w)&&(node[p->adjvex].dj-low<=w))
			{
				cost+=p->data+node[p->adjvex].weight-node[j].weight;
				if(min_cost>cost)min_cost=cost;
				dfs(p->adjvex);
			}
			p=p->next;
		}
	}
	cout<<min_cost<<endl;
}
int main()
{
	int i,j,k,t,u,v;
	cin>>i>>j;//输入等级差距和节点个数
	w=i;
	len=j;
	k=0;
	Arcnode *p;
	while(j--)
	{
		//输入金币数目和主人的等级，金币数目作为节点的权值
		cin>>node[k].weight>>node[k].dj>>t;
		//输入替代品的编号和优惠价格
		while(t--)
		{
			p=new(Arcnode);
			cin>>u>>v;
			p->adjvex=u-1;
			p->data=v;//优惠价格作为边的权值
			p->next=bian[k].first;
			bian[k].first=p;
		}
		k++;
	}

	high=low=node[0].dj;//原始等级

	BFS();//找最少的金币数目。
	system("pause");
	return 0;
}

• Re:我也是超内存啊 没有节操啊 (805) ls_smith 2012-07-27 16:52:39