POJ 1062 昂贵的聘礼【最短路】

港控/mmm° 2022-05-31 04:19 163阅读 0赞

## Best Deal ##

Time Limit: 1000MS Memory Limit: 10000K  
Total Submissions: 52564 Accepted: 15828

#### Description ####

> Tom, a young explorer, visited an Indian tribe and fell in love with the Chief’s daughter. Tom asked the Chief to marry his daughter to him. But the Chief would accept his proposal only if he could provide 10000 golden coins as the engagement gift. Tom couldn’t make it, so he pled for a reduction. The Chief said:” OK, I would then request 8000 golden coins if you could get me the fur coat of the Pontiff. Or, if you could get me his crystal, I could drop to 5000 golden coins.”
> 
> Tom then went to the Pontiff for his fur coat or crystal. The Pontiff too requested some amount of golden coins as the exchange, or a possible reduction of price if Tom could get him some other things. Tom continued to visit other people and found that all of them would either request some golden coins for exchange, or drop the price down for something else.
> 
> Now Tom needs your help on trading to marry the girl he loves.
> 
> An important rule Tom has to tell you is: the hierachical system is so strict in this tribe that two people will never contact each other in any way if the difference of the two levels they belong to is larger than a certain threshold. Tom is an outsider so he is beyond this restriction. However, if he trades with someone in a lower level, then others in a higher level will not trade with him anymore since otherwise they would be indirectly contacting the lower levels, and vice versa. Therefore your best suggestion to him must have all the situations considered.
> 
> For the sake of convenience, let us mark all the trading objects by numbers starting from 1. The Chief’s approval is as well considered an object and is always marked 1. Each object has a price P, the owner’s level L, and a sequence of substitutions Ti and the corresponding “voucher” price Vi. There must be no “indirect trading” if the difference between two levels is greater than M. You must calculate the least number of golden coins Tom needs to marry the daughter of the Chief.

#### Input ####

> The input consists of several test cases. For each test case:
> 
> The 1st line contains two integers M and N (1<=N<=100) which represent the threshold of level difference and the total number of trading objects respectively.  
> Then the descriptions of N objects follow, in the increasing order with respect to their marks. Each description begins with three nonnegative integers P, L, and X (< N), representing the object’s price, owner’s level, and the number of substitutions. The following X lines each contains two integers T and V, which are the mark number of the substitution and its “voucher” price, respectively.

#### Output ####

> For each test case, print in a single line the minimum number of golden coins needed.

#### Sample Input ####

> 1 4  
> 10000 3 2 //The Chief’s approval  
> 2 8000  
> 3 5000  
> 1000 2 1 //The Pontiff’s fur coat  
> 4 200  
> 3000 2 1 //The Pontiff’s crystal  
> 4 200  
> 50 2 0 //Another object

#### Sample Output ####

> 5250

题目链接（中文）：[http://poj.org/problem?id=1062][http_poj.org_problem_id_1062]

题意概括：  
　　一个人可以通过得到一个东西去抵另一个东西的价值，而交易的过程中他所交易的所有人，任意两人之间的等级差不能超过限定值。

解题分析：  
　　这道题最开始想到的是用搜索去做，没有过，后来才知道是最短路问题。因为最开始对于等级的限定规则没有理解清楚导致在判断条件时出错。最开始想的是把所有点到另一个点都判断一遍，只要这两个点超过限定值就把他俩标记为不能走，但是交上去WA了，后来才想明白这样处理不能保证一条路径上的任意两个点之间的等级限制都不超过限定值。只能先假定一个等级为最大等级，将所有比他大的等级和与他等级之差超过限定值的点都标记为走过，然后用dijkstra求出当前情况下的最少花费。遍历所有的等级最后比出最小花费输出。

#### AC代码： ####

#include<stdio.h>
    #include<math.h>
    #include<string.h>
    #include<algorithm>
    using namespace std;
    
    #define N 105
    #define inf 99999999
    
    struct nod{
        int id, price;
    };
    struct node{
        int price, level, len;
        struct nod h[N];
    }s[N];
    
    int e[N][N], dis[N], book[N];
    
    int dijkstra(int n)
    {
        int i, j, k, MIN;
        memset(dis, 0, sizeof(dis));
        for(i = 0; i <= n; i++) dis[i] = e[0][i];
        book[0] = 1;
        for(k = 1; k <= n; k++){
            MIN = inf;
            for(i = 1; i <= n; i++)
                if(!book[i] && dis[i] < MIN) MIN = dis[i], j = i;
            book[j] = 1;
            for(i = 1; i <= n; i++){
                if(!book[i] && dis[i] > e[j][i]+dis[j])
                    dis[i] = dis[j]+e[j][i];
            }
        }
        return dis[1];
    }
    
    int main()
    {
        int i, j, n, m, MIN;
        while(~scanf("%d%d", &m, &n)){
            for(i = 0; i <= n; i++){
                for(j = 0; j <= n; j++) e[i][j] = inf;
                e[i][i] = 0;
            }
            for(i = 1; i <= n; i++){
                scanf("%d%d%d", &s[i].price, &s[i].level, &s[i].len);
                e[0][i] = s[i].price;
                for(j = 1; j <= s[i].len; j++){
                    scanf("%d%d", &s[i].h[j].id, &s[i].h[j].price);
                    e[s[i].h[j].id][i] = s[i].h[j].price;
                }
            }
            MIN = inf;
            for(i = 1; i <= n; i++){
       //枚举所有等级
                memset(book, 0, sizeof(book));
                for(j = 1; j <= n; j++)//将所有比i点的等级大的点和与他等级之差超过限定值的点都标记为走过
                    if(s[j].level > s[i].level || fabs(s[i].level-s[j].level) > m) book[j] = 1;
                MIN = min(dijkstra(n), MIN);//选出最少花费
            }
            printf("%d\n",MIN);
        }
        return 0;
    }

[http_poj.org_problem_id_1062]: http://poj.org/problem?id=1062