POJ上难得一见的中文题……
思路：建立一个以0为源点的地图，那么Map[0][n]的值代表 第n号物品的价值，Map[i][j]代表用 j 替代 i 后，物品j的价值。我们认为酋长的承诺为节点 ‘1’ ，则我们需要做的就是通过一系列操作求出Map[0][1]的最小值，这时可以看出 这是一个最短路问题。题目还规定了，等级高的不会同意与等级低的交换，等级低的亦不会和高于自身m个级别的人交换，所以我们先来个简单的预处理：通过枚举1~N所有点作为最小等级，然后标记出所有非法点。
这样一来就是纯粹的最短路问题了。
#include<stdio.h>
#include<string.h>
#include<cstring>
#include<string>
#include<math.h>
#include<queue>
#include<algorithm>
#include<iostream>
#include<stdlib.h>
#include<cmath> #define INF 0x3f3f3f3f
#define MAX 1005 using namespace std; int vis[MAX],dist[MAX],n,m,Map[MAX][MAX]; struct node
{
int p,l,x;
}a[MAX]; int dij()
{
int i,j,minn,k; for(i=1;i<=n;i++)
dist[i]=Map[0][i]; for(i=1;i<n;i++)
{
minn=INF;
for(j=1;j<=n;j++)
{
if(!vis[j] && dist[j] < minn)
{
minn=dist[j];
k=j;
}
} vis[k]=1; for(j=1;j<=n;j++)
{
if(dist[j] > dist[k] + Map[k][j] && !vis[j])
dist[j]=Map[k][j]+dist[k];
}
} return dist[1];
} int main()
{
int i,j,x,w; while(scanf("%d%d",&m,&n)!=EOF)
{
for(i=0;i<MAX;i++)
for(j=0;j<MAX;j++)
Map[i][j]=INF; for(i=1;i<=n;i++)
{
scanf("%d%d%d",&a[i].p,&a[i].l,&a[i].x); Map[0][i]=a[i].p; for(j=1;j<=a[i].x;j++)
{
scanf("%d%d",&x,&w); Map[x][i]=w;
}
} int minn=INF; for(i=1;i<=n;i++)//枚举最小等级
{
for(j=1;j<=n;j++)
{
if(a[i].l < a[j].l || a[i].l-a[j].l > m)
vis[j]=1;//标记出非法点
else
vis[j]=0;
} minn=min(dij(),minn);
}
printf("%d\n",minn);
}
return 0;
}