本文主要是介绍poj 1062 昂贵的聘礼 最短路bellman，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
假设等级差距为1，货物1等级为1，货物2等级为2，货物等级3为3，若1先与2交易，则2无法与3交易，因为1与3相差2>1.
故使 每次使 pp[edge[j].v].minn=max(pp[edge[j].v].minn,pp[edge[j].u].minn);
pp[edge[j].v].maxx=min(pp[edge[j].v].maxx,pp[edge[j].u].maxx);
首先题目是有向图，没负权回路就没问题，很多人没看清题，discuss里题目争议很大，边权题意已经规定为正值，故不会形成负权回路。
代码
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
const int INF=0x1f1f1f;
int m,n;
struct Str
{int u;int v;int w;
};
Str edge[11000];
int len;
int res[110];
struct Point
{int p,l;int minn,maxx;
};
Point pp[110];
void bellman()
{memset(res,INF,sizeof(res));res[1]=0;for(int i=1;i<=n;i++){pp[i].minn=pp[i].l-m;pp[i].maxx=pp[i].l+m;}for(int i=0;i<n;i++){for(int j=0;j<len;j++){if(res[edge[j].v]>res[edge[j].u]+edge[j].w&&pp[edge[j].v].l>=pp[edge[j].u].minn&&pp[edge[j].v].l<=pp[edge[j].u].maxx){pp[edge[j].v].minn=max(pp[edge[j].v].minn,pp[edge[j].u].minn);pp[edge[j].v].maxx=min(pp[edge[j].v].maxx,pp[edge[j].u].maxx);res[edge[j].v]=res[edge[j].u]+edge[j].w;}}}
}
int main()
{while(scanf("%d%d",&m,&n)!=EOF){len=0;int p,l,x;for(int i=0;i<n;i++){scanf("%d%d%d",&p,&l,&x);pp[i+1].p=p;pp[i+1].l=l;int t,v;for(int j=0;j<x;j++){scanf("%d%d",&t,&v);edge[len].u=i+1;edge[len].v=t;edge[len++].w=v;}}bellman();int num=INF;for(int i=1;i<=n;i++){num=min(num,pp[i].p+res[i]);}cout<<num<<endl;}return 0;
}
/*
1 3
100 1 1
2 20
70 2 1
3 20
20 3 0
*/
这篇关于poj 1062 昂贵的聘礼 最短路bellman的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
