POJ上难得一见的中文题……

思路：建立一个以0为源点的地图，那么Map[0][n]的值代表 第n号物品的价值，Map[i][j]代表用 j  替代 i 后，物品j的价值。我们认为酋长的承诺为节点 ‘1’ ，则我们需要做的就是通过一系列操作求出Map[0][1]的最小值，这时可以看出 这是一个最短路问题。题目还规定了，等级高的不会同意与等级低的交换，等级低的亦不会和高于自身m个级别的人交换，所以我们先来个简单的预处理：通过枚举1~N所有点作为最小等级，然后标记出所有非法点。

这样一来就是纯粹的最短路问题了。

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #define INF 0x3f3f3f3f#define MAX 1005using 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
               
                 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
                
                  m) vis[j]=1;//标记出非法点 else vis[j]=0; } minn=min(dij(),minn); } printf("%d\n",minn); } return 0;}