题意：每个物品看成一个节点，酋长的允诺也看作一个物品， 如果一个物品加上金币可以交换另一个物品，则这两个节点之间有边，权值为金币数，求第一个节点到所有节点的最短路。
因为有等级限制，所以枚举每个点作为最低等级，选取符合所有符合等级限制的点最短路问题，不过因为存在着等级的差异所以需要枚举一下。本题的思路就是对冒险者的等级进行枚举，也就是说冒险者只能和在他等级以上的人进行交易。这样枚举的好处是能够把所有的情况都考虑进去。有一点需要注意：酋长的等级不一定是最高的
构图时要注意的是，酉长的承诺不是 最初的源点，它是一个目标点，也就是说点到点的指向方向是由 无替代品的点 逐渐指向到 酉长的承诺1点，题意说明的是一个回溯的过程，因此可以定义一个最初的源点0点，它到其他各点的权值就是每个物品的原价，而点A到点B的权值 就是 物品B在有第A号替代品情况下的优惠价
先回顾一下最短路算法：
本题我用的是dijkstra算法：
1 //昂贵的聘礼 2 #include3 #include 4 #include 5 #include 6 #include 7 using namespace std; 8 #define inf 0x7fffffff 9 int m,n;//地位等级限制，物品总数10 int price[101][101];//物品i在有第t号替代品情况下的优惠价pricr[t][i],当t=0时说明i无替代品，此时为原价11 int lv[101];//i号物品主人的等级12 int sum[101];//i号物品的替代品总数13 int dist[101];//相当于每件物品的原价14 bool bools[101];//标记物品是否被访问15 int dijkstra()16 {17 int node,minDist;18 for(int i=1;i<=n;i++)19 dist[i]=price[0][i];20 for(int i=1;i<=n;i++)21 {22 node=0;23 minDist=inf;24 for(int j=1;j<=n;j++)25 {26 if(!bools[j]&&minDist>dist[j])27 {28 minDist=dist[j];29 node=j;30 }31 }32 if(node==0)33 {34 break;35 }36 bools[node]=true;37 //松弛38 for(int j=1;j<=n;j++)39 {40 if(!bools[j]&&price[node][j]>0&&dist[j]>dist[node]+price[node][j])41 dist[j]=dist[node]+price[node][j];42 }43 }44 return dist[1];45 }46 int main()47 {48 memset(price,0,sizeof(price));49 memset(lv,0,sizeof(lv));50 memset(dist,inf,sizeof(dist));51 memset(bools,false,sizeof(bool));52 scanf("%d%d",&m,&n);53 for(int i=1;i<=n;i++)54 {55 scanf("%d%d%d",&price[0][i],&lv[i],&sum[i]);56 for(int j=1;j<=sum[i];j++)57 {58 int t,less;59 scanf("%d%d",&t,&less);60 price[t][i]=less;61 }62 }63 int minPrice=inf;64 int maxLv;65 int tempPrice;66 for(int i=1;i<=n;i++)67 {68 maxLv=lv[i];69 for(int j=1;j<=n;j++) //遍历其他各点70 {71 if(lv[j]>maxLv || maxLv-lv[j]>m)72 bools[j]=true;73 else74 bools[j]=false;75 }76 tempPrice=dijkstra();77 if(minPrice>tempPrice)78 minPrice=tempPrice;79 }80 printf("%d\n",minPrice);81 return 0;82 }