poj-1062昂贵的聘礼-Bellman-F

本文主要是介绍poj-1062昂贵的聘礼-Bellman-F，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

   中文题，说一下思路，就是把冒险者当成0点，各个物品的价格就是到各个点的距离，然后用BF松驰，要枚举等级差距，因为比如 国王的等级为3，还有两个等级分别为4，2的人，等级限置为1，先与1交易，再与4交易，就是间接接触，所以要去枚举，国王等级不一定是最高的

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define MAX 0x3f3f3f
int m, n,cont;
struct node
{int u, v, w;
}ls[5100];
int point[1500];
int jiage[150];
int bj[150];
int BF()
{int dis[110];for(int i = 1; i <= n; i++)dis[i] = jiage[i];for(int i = 0; i < n-1; i++){bool flag = false;for(int j = 0;j < cont; j++){if(bj[ls[j].u]&&bj[ls[j].v]){if(dis[ls[j].v] > dis[ls[j].u]+ls[j].w){dis[ls[j].v] = dis[ls[j].u]+ls[j].w;flag = true;}}}if(!flag)break;}return dis[1];}
int main()
{while(~scanf("%d%d",&m,&n)){cont = 0;memset(ls,0,sizeof(ls));memset(point,0,sizeof(point));for(int i = 1; i <= n; i++){int q,d,t;scanf("%d%d%d",&q,&d,&t);point[i] = d;jiage[i] = q;for(int j = 0; j < t; j++){int v, w;scanf("%d%d",&v,&w);ls[cont].u = v;ls[cont].v = i;ls[cont++].w = w;}}int MA = point[1];int ans = MAX;for(int i = 0; i <= m; i++){memset(bj,0,sizeof(bj));for(int j = 1; j<= n; j++){if(MA -point[j]<=(m-i) && (MA-point[j]+i)>=0)bj[j] = 1;}int x = BF();if(ans > x)ans = x;}printf("%d\n",ans);}return 0;
}

这篇关于poj-1062昂贵的聘礼-Bellman-F的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---