#include <iostream>
using namespace std;

typedef int INT;
typedef bool BOOL;
typedef char CHAR;
typedef double DOUBLE;
typedef float FLOAT;
typedef double D64;
typedef unsigned int U32;
typedef unsigned short int U16;
typedef unsigned char U8;

#define MaxGoods 100

INT Out;
INT levelLow,levelHigh,LevelLimit;

typedef struct
{
	U8 identifier;
	INT discountPrice;

}Succedaneum;
typedef struct
{
	INT price;//该物品的价值
	INT level;//物品主人的等级
	INT tmpShortest;//求最短路径过程的临时变量
	INT shortest;//该节点到到酋长节点的最短路径，可以不考虑 代码中没有用
	U8 outdegree;
	BOOL isVisited;
	Succedaneum target[MaxGoods];//由改物品可以换得的物品
}BridePrice;//物品节点

BOOL isInLevelLimit(INT level)
{
	if((levelLow - level) * (levelLow - level) > LevelLimit * LevelLimit)
		return false;
	if((levelHigh - level) * (levelHigh - level) > LevelLimit * LevelLimit)
		return false;
	return true;
}

void getShortest(U16 currentPrice,BridePrice *pBridePrice,U8 index,U8 sumOfgoods)
{
	U8 i,j,bIdx = 0xff,tIdx = 0xff;
	U32 tmpBridge = 0 - 1;
	BridePrice *bridePrice = pBridePrice + index;

	if(bridePrice ->level < levelLow)
		levelLow = bridePrice ->level;
	if(bridePrice ->level > levelHigh)
		levelHigh = bridePrice ->level;

	if( index == 0)
	{
		if(currentPrice < Out)
			Out = currentPrice;
		return;
	}
	bridePrice->isVisited = true;
	bridePrice->tmpShortest = currentPrice;
	for(i = 0;i < sumOfgoods;i++)
	{
		if(pBridePrice[i].isVisited == true)
			for(j = 0;j < pBridePrice[i].outdegree;j++)
			{
				if(pBridePrice[pBridePrice[i].target[j].identifier].isVisited == false)
					if(pBridePrice[i].tmpShortest + pBridePrice[i].target[j].discountPrice < tmpBridge
						&& isInLevelLimit(pBridePrice[pBridePrice[i].target[j].identifier].level))
					{
						tmpBridge = pBridePrice[i].tmpShortest + pBridePrice[i].target[j].discountPrice;
						bIdx = i;
						tIdx = pBridePrice[i].target[j].identifier;
					}
			}
	}
	if(bIdx != 0xff && tIdx != 0xff)
		getShortest(tmpBridge,pBridePrice,tIdx,sumOfgoods);
}

int main()
{
	INT levelLimit;
	INT sumOfgoods;
	INT sumOfsuccedaneum,identifier,discountPrice;
	U32 result = 0;
	BridePrice *bridePrice;
	INT i,j;

	scanf("%d%d",&levelLimit,&sumOfgoods);
	bridePrice = new BridePrice[sumOfgoods];
	for(i = 0;i < sumOfgoods;i++)
	{
		bridePrice[i].isVisited = false;
		bridePrice[i].outdegree = 0;
		bridePrice[i].tmpShortest = bridePrice[i].shortest = 0;
	}

	for(i = 0;i < sumOfgoods;i++)
	{
		scanf("%d%d%d",&bridePrice[i].price,&bridePrice[i].level,&sumOfsuccedaneum);

		for(j = 0;j < sumOfsuccedaneum;j++)
		{
			scanf("%d%d",&identifier,&discountPrice);
			identifier --;
			bridePrice[identifier].target[ bridePrice[identifier].outdegree ].identifier = i;
			bridePrice[identifier].target[ bridePrice[identifier].outdegree ].discountPrice = discountPrice;
			bridePrice[identifier].outdegree ++;
		}
	}

	Out = bridePrice[0].price;
	LevelLimit = levelLimit;

	for(i = 1;i < sumOfgoods;i++)
	{
		levelLow = levelHigh =  bridePrice[0].level;

		getShortest(bridePrice[i].price,bridePrice,i,sumOfgoods);

		bridePrice[i].shortest = Out;
		for(j = 0;j < sumOfgoods;j++)
		{
			bridePrice[j].isVisited = false;
			bridePrice[j].tmpShortest = 0;
		}
	}

	printf("%d\n",Out);
}

• Re:各种测试数据 都过了，就是wa，求反例~ (3564) hu_wu 2013-05-29 16:54:37