这题算是我自己做的了，从开始建模构图构思，敲代码，调试，重新想思路。虽然做这题做了很久，但是也算是了结了我的一个心愿吧，昂贵的聘礼是我从ACM入门时就开始想做掉的题目了，这次下了决心终于做掉了，开心啊~
---------------------------------------------------分割线-----------------------------------------------------------
这题可以用最短路径的方法来做，A，B物品能够换则有一条带权边。边的值为A换B的价格，这题是有向边，所以付边值时不能两边同时改值。另外这题的关键之处在于构图与等级限制。开始我写的是酋长以下到M的等级范围，WA了，这也就是我不懂为啥要枚举等级的原因了。因为酋长的等级不一定是最高的，所以规定一个范围，在此范围中的等级间可以进行交易，交易的结果就是对图进行修改。这里用了保留整个图的思想，就是只改变[0][i]的值而整个图并没有什么变化。下次运算也同样进行即可。原物品有一个价值，于是我便把该点的价值联系到[i][120]的边权值，这样便能够形成一个符合题意的图了。
另外要注意的是最大最小值的赋值，这里又WA了一次，最小值一定要取得比题中数据大，防止发生悲剧。
#include<iostream>
#include<cmath>
#define MAXN 121
#define INF (1<<30)
using namespace std;int dij[MAXN][MAXN];
int level[MAXN];
int N,M;void dijstra( int up,int down )
{int i,j,k;bool visited[MAXN];memset( visited,0,sizeof(visited) );dij[1][0]=dij[0][1]=0;visited[0]=true;for( i=2;i<MAXN;i++ )dij[0][i]=dij[i][0]=INF;k=0;for( i=1;i<=N;i++ ){int min=INF;for( j=1;j<=N;j++ )if( !visited[j] && min>dij[0][j] ){min=dij[0][j];k=j;}visited[k]=true;for( j=1;j<=N;j++ )if( dij[0][j]>dij[0][k]+dij[k][j] && ( level[j]<=up&&level[j]>=down ) )dij[0][j]=dij[0][k]+dij[k][j];}
}int main()
{int i,j;while( scanf( "%d %d",&M,&N )!=EOF ){memset( dij,0x7F,sizeof(dij) );memset( level,0,sizeof(level) );level[120]=100;int maxLevel=0;int minLevel=INF;int min=INF;for( i=1;i<=N;i++ ){int a,b,c;scanf( "%d %d %d",&a,&b,&c );dij[i][120]=a;level[i]=b;maxLevel=maxLevel>b?maxLevel:b;minLevel=minLevel>b?b:minLevel;for( j=1;j<=c;j++ ){scanf( "%d%d",&a,&b );dij[i][a]=b;}}while( maxLevel>=0 ){if( ( level[1]<=maxLevel&&level[1]>=maxLevel-M ) )dijstra( maxLevel,maxLevel-M );maxLevel--;dij[0][1]=dij[1][0]=0;for( i=1;i<=N;i++ )if( min>dij[0][i]+dij[i][120] )min=dij[0][i]+dij[i][120];}printf( "%d\n",min );}return 0;
}