2009-2-28pku1062.txt

数据结构中的单元最短路径算法的题目和源代码！其中所有的题目都能在PKU上找的到！

/*
解题思路:
增加一个起点S, 若某物品Ai的价格为Pi, 添一条权值为Pi的边S-->Ai
若物品Aj可以用Ai加优惠价Qi换得,加权值为Qi的边Ai-->Aj
除了S,每个点都有一个rank,枚举rank最大的点(从1到n),不妨设其rank值为R0,除去rank大于R0的,以及rank小于R0-m的.
在剩余的图中求S到A1的最短路.
*/
#include<stdio.h>
const int MAXV=105;
const int MAXE=5460;
const int INF=0x6fffffff;
typedef struct Edge
{
	int st;
	int ed;
	int distance;
}Edge;
Edge edge[MAXE];
int d[MAXV];
int use[MAXV];
int rank[MAXV];
//初始化d[u]：用来描述从源点S到u的最短路径上权值的三界！
void Init(int V,int S)
{
	int i;
	for(i=1;i<=V;i++)
		d[i]=INF;//开始的时候设置为无穷大!
	d[S]=0;//源点设置为0
}
//Bellman_Ford算法的实现!
bool Bellman_Ford(int V,int E,int S)
{
	int i,j;
	bool relaxed;//优化
	Init(V,S);
	for(i=1;i<=V-1;i++)
	{
		relaxed=true;
		for(j=1;j<=E;j++)
			if(use[edge[j].ed]&&d[edge[j].ed]>d[edge[j].st]+edge[j].distance)
				d[edge[j].ed]=d[edge[j].st]+edge[j].distance,relaxed=false;
		if(relaxed)//说明当前这一轮没有进行松弛，那么以后将也不会进行松弛，所以就提前结束！
			break;
	}
	return relaxed;
}
int main()
{
	int i,j,max,p,st,distance,x,V,M,E;
	while(scanf("%d%d",&M,&V)!=EOF)
	{
		E=0;
		for(i=1;i<=V;i++)
		{
			scanf("%d%d%d",&p,&rank[i],&x);
			edge[++E].st=V+1,edge[E].ed=i,edge[E].distance=p;
			while(x--)
			{
				scanf("%d%d",&st,&distance);
				edge[++E].st=st,edge[E].ed=i,edge[E].distance=distance;
			}
		}
		max=INF;
		for(i=1;i<=V;i++)
		{
			for(j=1;j<=V;j++)
				if(rank[j]>rank[i]||rank[i]-rank[j]>M)
					use[j]=0;
				else
					use[j]=1;
				Bellman_Ford(V+1,E,V+1);
				if(max>d[1])
					max=d[1];
		}
		printf("%d\n",max);
	}
	return 0;
}
/*
1 4
10000 3 2
2 8000
3 5000
1000 2 1
4 200
3000 2 1
4 200
50 2 0


5250
*/