昂貴的聘禮

Time Limit: 1000MS	?	Memory Limit: 10000K
Total Submissions: 41066	?	Accepted: 11959

Description

年輕的探險家來到了一個印第安部落里。在那里他和酋長的女兒相愛了，于是便向酋長去求親。酋長要他用10000個金幣作為聘禮才答應把女兒嫁給他。

探險家拿不出這么多金幣，便請求酋長減少要求。酋長說："嗯，假設你能夠替我弄到大祭司的皮襖。我能夠僅僅要8000金幣。假設你能夠弄來他的水晶球，那么僅僅要5000金幣即可了。

"探險家就跑到大祭司那里，向他要求皮襖或水晶球，大祭司要他用金幣來換，或者替他弄來其它的東西。他能夠減少價格。探險家于是又跑到其它地方。其它人也提出了類似的要求，或者直接用金幣換。或者找到其它東西就能夠減少價格。只是探險家不是必需用多樣東西去換一樣東西，由于不會得到更低的價格。

探險家如今非常須要你的幫忙。讓他用最少的金幣娶到自己的心上人。

另外他要告訴你的是。在這個部落里。等級觀念十分森嚴。地位差距超過一定限制的兩個人之間不會進行不論什么形式的直接接觸。包含交易。

他是一個外來人，所以能夠不受這些限制。

可是假設他和某個地位較低的人進行了交易，地位較高的的人不會再和他交易，他們覺得這樣等于是間接接觸。反過來也一樣。因此你須要在考慮全部的情況以后給他提供一個最好的方案。

為了方便起見。我們把全部的物品從1開始進行編號，酋長的允諾也看作一個物品，而且編號總是1。

每一個物品都有相應的價格P。主人的地位等級L，以及一系列的替代品Ti和該替代品所相應的"優惠"Vi。假設兩人地位等級差距超過了M。就不能"間接交易"。你必須依據這些數據來計算出探險家最少須要多少金幣才干娶到酋長的女兒。

Input

輸入第一行是兩個整數M，N（1 <= N <= 100）。依次表示地位等級差距限制和物品的總數。接下來依照編號從小到大依次給出了N個物品的描寫敘述。

每一個物品的描寫敘述開頭是三個非負整數P、L、X（X < N），依次表示該物品的價格、主人的地位等級和替代品總數。接下來X行每行包含兩個整數T和V，分別表示替代品的編號和"優惠價格"。

Output

輸出最少須要的金幣數。

Sample Input

1 4 10000 3 2 2 8000 3 5000 1000 2 1 4 200 3000 2 1 4 200 50 2 0

Sample Output

5250

Source

//這道是中文題,我居然還理解錯了題意.本題的等級差是指? : 最高等級與最低等級的差值,并非每兩個人之間的差值.

#include <iostream> #include <algorithm> #include <stdio.h> #include <string.h> #include <queue> #include <vector> #define ll long long #define inf 0x3f3f3f3fusing namespace std; int n,m; struct node{int p;int l;int x; }a[110]; struct Nd{int num;int money; }now; int s,e; vector<Nd>vec[110]; int vis[110]; int dis[110]; int ans; void spfa(){memset(vis,0,sizeof(vis));memset(dis,inf,sizeof(dis));queue<int>q;q.push(1);vis[1] = 1;dis[1] = a[1].p;while(!q.empty()){int u = q.front();q.pop();vis[u] = 0;for(int i = 0; i < vec[u].size(); ++i){now = vec[u][i];if(dis[now.num] > dis[u]-a[u].p+a[now.num].p+now.money&&a[now.num].l>=s && a[now.num].l<=e){dis[now.num] = dis[u]-a[u].p+a[now.num].p+now.money;if(!vis[now.num]){vis[now.num] = 1;q.push(now.num);}}}}for(int i = 1; i <= n; ++i){ans = min(ans,dis[i]);} } int main() {while(~scanf("%d%d",&m,&n)){for(int i = 0; i <= n; ++i){vec[i].clear();}for(int i = 1; i <= n; ++i){scanf("%d%d%d",&a[i].p,&a[i].l,&a[i].x);for(int j = 0; j < a[i].x; ++j){scanf("%d%d",&now.num,&now.money);vec[i].push_back(now);}}ans = inf;for(int i = a[1].l-m; i <= a[1].l; ++i){s = i;e = i+m;spfa();}printf("%d\n",ans);}return 0; }

#include<iostream> #include<cstdio> #include<cstring> #include<cstdlib> #include<cmath> #define INF 200000000using namespace std;struct node {int u,v,w; } edge[10000]; int num=0; int N,M; int P[2000],L[2000],n[2000]; int t,v; int low[2000],a,b; int has[2000] ; int Bellman(int u0) {for(int i=0; i<=N; i++)low[i]=INF;low[u0]=0;for(int i=0; i<N-1; i++){int flag=0;for(int j=0; j<num; j++){if(has[edge[j].u]&&has[edge[j].v]&&low[edge[j].u]+edge[j].w<low[edge[j].v]){low[edge[j].v]=low[edge[j].u]+edge[j].w;flag=1;}}if(flag==0)break;}int Min=INF;for(int i=1; i<=N; i++){low[i]+=P[i]; //最小價格為優惠價+擁有優惠價須要花多少錢if(Min>low[i])Min=low[i];}//printf("%d\n",Min);return Min; } int main() {//freopen("in.txt","r",stdin);while(~scanf("%d%d",&M,&N)){num=0;for(int i=1; i<=N; i++){scanf("%d%d%d",&P[i],&L[i],&n[i]);for(int j=1; j<=n[i]; j++){int a,b;scanf("%d%d",&a,&b);edge[num].u=i;edge[num].v=a;edge[num++].w=b; //存入優惠的價格}}int ans=L[1];int Min=INF;//最高等級的與最低的等級差不會超過Mfor(int i=0; i<=M; i++){memset(has,0,sizeof(has));for(int j=1; j<=N; j++){if(ans-L[j]<=M-i&&L[j]-ans<=i){has[j]=1;}}int k=Bellman(1);if(Min>k)Min=k;}printf("%d\n",Min); } }

轉載于:https://www.cnblogs.com/jzssuanfa/p/7061618.html

總結

以上是生活随笔為你收集整理的poj1062 Bellman 最短路应用的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。