POJ 1062 昂贵的聘礼

Posted on | In | 阅读

每个物品是一个节点，当前dis是直接用钱换的价值，从被申请交换的物品向申请交换的物品方向建边，边权是交换后还需要的优惠价。至于等级的限制，因为最后一定要和酋长交换，否则答案就是酋长给出的原价，所以将所有包含酋长的等级长为m的区间都枚举出来，求所有点到酋长的最短路，spfa就直接把所有点push一遍到queue中就行。

C++ Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <string.h>
#include <queue>
#include <math.h>
#define MAX_NODE 101
#define INF 0x7fffffff


using namespace std;

int arr[MAX_NODE][MAX_NODE];
int ranks[MAX_NODE];
int cost[MAX_NODE];
int dis[MAX_NODE];
bool isInqueue[MAX_NODE];


int m, n;
int p, l, x;
int t, v;

bool spfa(int pos){
    memset(isInqueue, 0, sizeof(isInqueue));
    queue<int> q;
    for(int i = 1; i <= n; i++){
        dis[i] = cost[i];
        if(ranks[i] >= ranks[1]-m+pos && ranks[i] <= ranks[1]+pos){
            q.push(i);
            isInqueue[i] = true;
        }
    }
    while(!q.empty()){
        int cur = q.front();
        q.pop();
        isInqueue[cur] = false;
        for(int i = 1; i <= n; i++){
            if(arr[cur][i] > 0 && (ranks[i] >= ranks[1]-m+pos && ranks[i] <= ranks[1]+pos)){
                if(dis[i] > arr[cur][i] + dis[cur]){
                    dis[i] = arr[cur][i] + dis[cur];
                    if(!isInqueue[i]){
                        isInqueue[i] = true;
                        q.push(i);
                    }
                }
            }
        }
    }
}

int main(){
    while(~scanf("%d%d", &m, &n)){
        memset(arr, -1, sizeof(arr));
        for(int i = 1; i <= n; i++){
            scanf("%d%d%d", &p, &l, &x);
            cost[i] = dis[i] = p;
            ranks[i] = l;
            for(int j = 0; j < x; j++){
                scanf("%d%d", &t, &v);
                arr[t][i] = v;
            }
        }
        int mi = INF;
        for(int i = 0; i <= m; i++){
            spfa(i);
            mi = min(mi, dis[1]);
        }
        printf("%d\n", mi);
    }
    return 0;
}