您现在的位置是:首页 > 学习之路 > ACM||算法ACM||算法

POJ 1062 昂贵的聘礼

卞振伟2019-07-25【ACM||算法】人已围观

简介POJ 1062 昂贵的聘礼


题意:
地位等级差距限制m和物品的总数n。接下来按照编号从小到大依次给出了n个物品的描述,
物品的价格val、主人的地位等级、Rank和替代品总数k。接下来k行表示替代品的编号t和"优惠价格"v。
问怎么样选取可以让你的花费最少来购买到物品1
思路:
假设一个0号物品,求由0号物品换到1号物品的花费。
关于等级限制,无法确定酋长是否是最高等级,于是可以将0号物品依次设为n个物品的等级,
并假设0号物品

#include<algorithm>
#include<iostream>
#include<cstring>

using namespace std;

const int maxn = 110;
const int inf = 0x3f3f3f3f;
int m, n;
int G[maxn][maxn];
int vst[maxn];
int d[maxn];
int val[maxn];
int Rank[maxn];

bool check(int i){
    if(Rank[i] >= Rank[0] && Rank[i] - Rank[0] <= m)
        return true;
    return false;
}

int dijkstra(){
    for(int i = 0; i < maxn; ++i){
        vst[i] = 0;
        d[i] = inf;
    }
    for(int i = 1; i <= n; ++i)
        d[i] = val[i];

    for(int i = 0; i < n; ++i){
        int k = 0, Min = inf;
        for(int j = 1; j <= n; ++j){
            if(!vst[j] && Min > d[j]){
                Min = d[j];
                k = j;
            }
        }

        vst[k] = 1;
        if(!check(k))
            continue;
        for(int j = 1; j <= n; ++j){
            if(!vst[j] && check(j) && d[j] > d[k] + G[k][j])
                d[j] = d[k] + G[k][j];
        }

    }
    return d[1];
}

int main(){
    cin >> m >> n;
    for(int i = 0; i < maxn; ++i)
        for(int j = 0; j < maxn; ++j)
            G[i][j] = inf;

    for(int i = 1; i <= n; ++i){
        int k, t, v;
        G[i][i] = 0;
        cin >> val[i] >> Rank[i] >> k;
        while(k--){
            cin >> t >> v;
            G[t][i] = v;
        }
    }

    int ans = inf;
    for(int i = 1; i <= n; ++i){
        Rank[0] = Rank[i];
        ans = min(ans, dijkstra());
    }

    cout << ans << endl;

    return 0;
}

Tags:ACM   编程   个人   题解   算法   C|C++

很赞哦! ()

上一篇:POJ 2502 Subway

下一篇:POJ 1847 Tram

文章评论

站点信息

  • 建站时间:2018-11-25
  • 网站程序:帝国CMS7.5
  • 文章统计:118篇文章
  • 标签管理标签云
  • 统计数据百度统计
  • 网站地图XML网站地图
  • 微信公众号:扫描二维码,关注我的公众号
  • GitHub:扫描二维码,关注我的GitHub

客服在线

QQ客服

客服微信扫码

服务时间

周一至周日 9:00-21:00