#include <iostream>

using namespace std;

#define MAX 9999999
int M,N,mMin;
int F[101]; //序号为i的物品的最小花费
int P[101];//序号为i的物品的价格
int L[101]; //序号为i的物品 的地位
int X[101][20000];//X[i][0]为物品i的可交换物品数目，X[i][k]为可交换物品的序号，X[i][k]为可交换物品的价格

int main()
{
	while(scanf("%d",&M)!=EOF)
	{
  mMin=MAX;
  scanf("%d",&N);
  for(int j=1;j<=N;j++)
  {
	  scanf("%d %d %d",&P[j],&L[j],&X[j][0]);
	  for(int k=1;k<=X[j][0]*2;k+=2)
	  {
      scanf("%d %d",&X[j][k],&X[j][k+1]);
	  }
  }



  for(int t=L[1]-M;t<=L[1];t++)
  {
   memset(F,MAX,sizeof(int)*101);
  for(int j=N;j>=1;j--)
  {
    if(L[j]>t+M||L[j]<t) //过滤人物
		continue;

	F[j]=P[j];
	for(int k=1;k<=X[j][0]*2;k+=2)
	{
     F[j]=min(F[j],F[X[j][k]]+X[j][k+1]);//DP
	}

  }
  if(mMin>F[1])
  mMin=F[1];

  }



  printf("%d\n",mMin);
 }
return 0;
}

• Re:比dijkstra慢，但更容易写的DP解法 (32) my_echo 2009-12-02 12:16:13
  • Re:比dijkstra慢，但更容易写的DP解法 (14) donkeyinacm 2009-12-02 13:15:34
• 有错 Re:比dijkstra慢，但更容易写的DP解法 (47) treert 2010-12-02 22:45:46