poj/1062.cpp at master · aimfly/poj · GitHub

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
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

typedef struct _replace_thing{
    int id;
    int price;
} replace_thing;

typedef struct _thing{
    int price;
    int owner_level;
    vector<replace_thing> replace_things;
    int checking;
} thing;

vector<thing> things;
int m;
int get_min_price(int id,int max_level,int min_level){
    if(things[id].checking==1)return -1;
    if(things[id].owner_level<min_level){
        min_level=things[id].owner_level;
    }else if(things[id].owner_level>max_level){
        max_level=things[id].owner_level;
    }
    if(max_level-min_level>m)return -1;
    things[id].checking=1;
    int min_price=things[id].price;
    int total_price;
    int tmp_price=0;
    for(int i=0;i<things[id].replace_things.size();i++){
        if(min_price<things[id].replace_things[i].price)continue;
        tmp_price=get_min_price(things[id].replace_things[i].id,max_level,min_level);
        if(tmp_price==-1)continue;
        total_price=tmp_price+things[id].replace_things[i].price;
        if(min_price>total_price){
            min_price=total_price;
        }
    }
    things[id].checking=0;
    return min_price;
}

int main(){
    int n;
    int master_lever;
    int p,l,x,t,v;
    cin>>m>>n;
    thing tmp_thing;
    replace_thing tmp_replace;
    for(int i=0;i<n;i++){
        cin>>p>>l>>x;
        tmp_thing.price=p;
        tmp_thing.owner_level=l;
        tmp_thing.replace_things.clear();
        tmp_thing.checking=0;
        for(int j=0;j<x;j++){
            cin>>t>>v;
            tmp_replace.id=t-1;
            tmp_replace.price=v;
            tmp_thing.replace_things.push_back(tmp_replace);
        }
        things.push_back(tmp_thing);
    }
    int min_price=get_min_price(0,things[0].owner_level,things[0].owner_level);
    cout<<min_price<<endl;
    return 0;
}