#include <iostream>
#include <string.h>
#define MAXN 201
#define INF 3276799
using namespace std;
int adj[MAXN][MAXN];
int d[MAXN];
int v[MAXN];
int level[MAXN];
int  M,N,P,L,X;
void Init()
{
	memset(adj,0,sizeof(adj));
	memset(level,0,sizeof(level));
	for(int i=1;i<=N;i++)
	{
		cin>>P>>L>>X;
		adj[0][i]=P;
		level[i]=L;
		for(int k=0;k<X;k++)
		{
			int a,price;
			cin>>a>>price;
			adj[a][i]=price;
		}
	}
}
void Dij(int downL ,int upL) //限制在[downL,upL]间的人可以交易
{
	memset(v,0,sizeof(v));
	for(int i=1;i<=N;i++)
		d[i]=adj[0][i];
	for(int i=1;i<=N;i++)
	{
		int x=1,m=INF;
		for(int y=1;y<=N;y++)
		{ 
			if(!v[y]&&d[y]<=m&&level[y]>=downL&&level[y]<=upL) m=d[x=y];
		}
		v[x]=1;
		for(int y=1;y<=N;y++)
			if(!v[y] && adj[x][y]!=0&&d[x]+adj[x][y]<d[y]&&level[y]>=downL&&level[y]<=upL)//
			{
					d[y]=d[x]+adj[x][y];
			}
	}
}
int main()
{
	while(cin>>M>>N)
	{
	     Init();
		 int min=INF;
		// int down=level[1]-M<1?1:level[1]-M;
		 int down=level[1]-M;  //fuck 题目中的等级还可以为负啊
		 for(int i=down;i<=level[1];i++)
		 {  
             Dij(i,i+M);
			 if(d[1]<min)
				 min=d[1];
		 }
	    cout<<min<<endl;
	}

}

• Re:等级还有可能是负数 ， (65) 911016 2011-04-13 09:51:34
  • Re:等级还有可能是负数 ， (65) 1000012801 2011-07-18 15:06:51