#include<cstdio>
#include<queue>
#include<cstring>

using namespace std;
/*********************前向星*********************/
const int maxe=20000;
const int maxn=101;
struct 
{
	int pre,to,w;
}edge[maxe];//所有边的内存池
struct  
{
	int val;
	int rank;
}nodeData[maxn];//结点的数据
int lenth=0;
int box[maxn];//总记录他最后一条边的地址
int n,e;//结点数，边数
void addDirectedPath(int from,int to,int w)
{
	edge[lenth].to = to;
	edge[lenth].pre = box[from];
	edge[lenth].w = w;
	box[from] = lenth++;
}

void iniList()
{
	lenth=1;
	memset(box,-1,sizeof(box));
	edge[0].pre=-1;
	edge[0].to = -1;
}
#define DEFAULTVALUE 0x1f1f1f1f

class qnode
{
public:
	int to;
	int v;
	int topRank;
	int bottomRank;
	qnode(int tt,int vv,int br,int tr):to(tt),v(vv),topRank(tr),bottomRank(br){}
	bool operator < (const qnode& other)const
	{
		return v> other.v;
	}
};
void iniDjstra(int *cost)
{
	memset(cost,0x1f,sizeof(int)*(n+1));
	//memset(vis,0,sizeof(char)*(n+1));
}
//整条路径的等级差不能超过rd
void djstra(int *cost,int start,int rd)
{
	qnode cur(start,nodeData[start].val,nodeData[start].rank,nodeData[start].rank);
	priority_queue<qnode> pq;
	int lpds;
	int neval;
	int topRank,bottomRank;
	pq.push(cur);
	cost[start] = nodeData[start].val;
	while(!pq.empty())
	{
		cur = pq.top();
		pq.pop();
		//vis[cur.to] = 1;
		for(lpds = box[cur.to];lpds!=-1;lpds = edge[lpds].pre)
		{
			topRank = cur.topRank>nodeData[edge[lpds].to].rank?cur.topRank:nodeData[edge[lpds].to].rank;
			bottomRank = cur.bottomRank < nodeData[edge[lpds].to].rank?cur.bottomRank:nodeData[edge[lpds].to].rank;
			if(topRank-bottomRank<=rd)
			{
				neval = cur.v - nodeData[cur.to].val  + edge[lpds].w + nodeData[edge[lpds].to].val;
				if(cost[edge[lpds].to] > neval)
				{
					cost[edge[lpds].to] = neval;
					pq.push(qnode(edge[lpds].to,neval,bottomRank,topRank));
				}
			}
		}
	}
}

int main()
{
	int difference,numberOfItems;
	//int mxRank=-1,indexOfItemForMxRank=-1;
	int i;
	int val,rank,numberOfSubstitutes;
	int index,concessionalPrice;
	int cost[maxn];
	//char vis[maxn];
	iniList();
	while(~scanf("%d%d",&difference,&numberOfItems))
	{
		n = numberOfItems;
		for(i=1;i<=numberOfItems;i++)
		{
			scanf("%d%d%d",&val,&rank,&numberOfSubstitutes);
			nodeData[i].rank = rank;
			nodeData[i].val = val;
			while(numberOfSubstitutes--)
			{
				scanf("%d%d",&index,&concessionalPrice);
				addDirectedPath(i,index,concessionalPrice);
			}
		}
		iniDjstra(cost);
		djstra(cost,1,difference);
		int minCost = 0x1f1f1f1f;
		for(i=1;i<=n;i++)
		{
			if(minCost>cost[i])minCost = cost[i];
		}
		printf("%d\n",minCost);
	}
	return 0;
}

• Re:附上反例 (253) wangchangbao 2013-04-20 13:22:21