（dijckstra）昂贵的聘礼

聘礼"/>

（dijckstra）昂贵的聘礼

题目链接

POJ 1062

题目大意

酋长要他用10000个金币作为聘礼才答应把女儿嫁给他。探险家拿不出这么多金币，便请求酋长降低要求。酋长说："嗯，如果你能够替我弄到大祭司的皮袄，我可以只要8000金币。如果你能够弄来他的水晶球，那么只要5000金币就行了。"探险家就跑到大祭司那里，向他要求皮袄或水晶球，大祭司要他用金币来换，或者替他弄来其他的东西，他可以降低价格。探险家于是又跑到其他地方，其他人也提出了类似的要求，或者直接用金币换，或者找到其他东西就可以降低价格。
最后计算最少需要多少金币
布吉岛怎么描述了，本来以为是个中文题会很简单的，没想到，呜呜呜，连汉字都看不懂了(￣_￣|||)

思路

做了好久啊这个题，主要是一开始题意不理解
▶ 最最重要的地方：

地位差距超过一定限制的两个人之间不会进行任何形式的直接接触，包括交易。他是一个外来人，所以可以不受这些限制。但是如果他和某个地位较低的人进行了交易，地位较高的的人不会再和他交易，他们认为这样等于是间接接触，反过来也一样。
酋长的地位等级也不一定是最高的

就是说，假设酋长的等级为L，误差在M之内，那么在[L-M,L+M]之间的人都是可以的，但是，在选择这些人的时候，任意两个人之间的差距不能超过M，比如选一个是L-M的人，一个是L+M的人，就是不可以的
所以，（在看了别的大神的解题思路之后） ，一个思路就是，一个个枚举符合的区间，求出在这个区间内最小的（用的是dijckstra算法），再求出所有区间内最小的

代码

#include <iostream>
#include <string>
#include <string.h>
#include <algorithm>
#define maxx 110
#define MM 99999999
using namespace std;
int road[maxx][maxx];
int price[maxx],level[maxx];
int divv[maxx],limit[maxx];
bool vis[maxx];
int M,N;int dij()
{memset(vis, 0, sizeof(vis));for (int i = 1; i <= N; i++) divv[i] = MM;divv[1] = 0;for (int i = 1; i <= N; i++){int mm = MM;int pos;for (int j = 1; j <= N; j++){if (divv[j] <= mm && !vis[j] && limit[j]){mm = divv[j];pos = j;}}vis[pos] = 1;for (int j = 1; j <= N; j++){if (limit[j]){divv[j] = min(divv[j], divv[pos] + road[pos][j]);}}}int ans = MM;for (int i = 1; i <= N; i++){divv[i] += price[i];ans = min(ans, divv[i]);}return ans;
}int main()
{cin>>M>>N;//完成数据的输入for(int i=1; i<=N; i++)for(int j=1; j<=N; j++)road[i][j] = MM;for(int q=1; q<=N; q++){int x;cin>>price[q]>>level[q]>>x;road[q][q] = 0;while(x--){int num,p;cin>>num>>p;// road[num][q] = p;road[q][num] = p;}}int klevel = level[1];int ans = MM;for(int i=0; i<=M; i++){memset(limit,0,sizeof(limit));for(int j=1; j<=N; j++){if(level[j] >= klevel-M+i && level[j] <=klevel+i){limit[j] = 1;}}ans = min(ans,dij());}cout<<ans<<endl;return 0;
}