MemoryGarden's Blog

努力 -----------大能猫

C++博客 首页 新随笔 联系 聚合 管理
  118 Posts :: 11 Stories :: 20 Comments :: 0 Trackbacks

http://acm.pku.edu.cn/JudgeOnline/problem?id=1062

题意 :中文的。。。。

想法 :将冒险者看成地n + 1 个点, 进行构图,用dj 最短路解决

一个物品的价钱就是n + 1 个点 与这个物品的边,而可以代替并便宜的物品的便宜价格是代替品到这个物品的距离,这样构图完毕。

等级限制自己没有想出来,看了一些报告,最后枚举可能性,也就是说,最后要和酋长交易,那么,等级的差别就可以围绕酋长的等级来算,也就是说,如果酋长的等级是3, 等级限制是2, 那么,这次交易要想成功,可能的等级是 1 2 3 , 2 3 4, 3 4 5 在应用dj 的时候,把等级不符合要求的点在图中去掉,也就是说,可以把它们先划分到已知的集合 s[i]里面去,这样,再进行路径扩展的时候,就不会加到这个点了。

所以,枚举可能性,重新构图,得到dj最短路的最小值, 便是结果

 1 #include <stdio.h>
 2 #include <string.h>
 3 #define max 102
 4 #define MAX 999999999
 5 using namespace std;
 6 int lv, n, map[max][max], tmap[max][max], rank[max], trank[max], ok[max], s[max], d[max];
 7 int dj(int x){
 8     int i, j, w, min;
 9     memset(s, 0sizeof(s));
10     memset(d, -1sizeof(d));
11     for(i = 1; i <= n + 1; i++){
12         if(map[x][i])d[i] = map[x][i];
13         if(!ok[rank[i]]){
14             s[i] = 1;
15             d[i] = MAX;
16         }
17     }
18     while(1){
19         w = -1;
20         for(i = 1; i <= n + 1; i++){
21             if(!s[i] && d[i] >= 0){
22                 if(w == -1 || d[i] < min){
23                     min = d[i];
24                     w = i;
25                 }
26             }
27         }
28         if(w == -1)break;
29         s[w] = 1;
30         for(i = 1; i <= n + 1; i++){
31             if(map[w][i]){
32                 if(d[i] < 0 || d[i] > d[w] + map[w][i])
33                     d[i] = map[w][i] + d[w];
34             }
35         }
36     }
37     return d[1];
38 }
39 int main(){
40     int i, j, u, v, w, res, cost, nlv, t, l, r, xx;
41     while(scanf("%d%d"&lv, &n) != -1){
42         res = MAX;
43         memset(map, 0sizeof(map));
44         memset(tmap, 0sizeof(tmap));
45         for(i = 1; i <= n; i++){
46             scanf("%d%d%d"&cost, &nlv, &t);
47             tmap[n + 1][i] = map[n + 1][i] = cost;
48             rank[i] = trank[i] = nlv;
49             for(j = 1; j <= t; j++){
50                 scanf("%d%d"&u, &cost);
51                 map[u][i] = tmap[u][i] = cost;
52             }
53         }
54         trank[n + 1= rank[n + 1= trank[1= rank[1];
55         for(l = lv, r = 0; l >= 0; l--, r++){
56             xx = 0;
57             memset(ok, 0sizeof(ok));
58             for(i = l; i > 0; i--){
59                 if(rank[1- i >= 0)
60                 ok[rank[1- i] = 1;
61             }
62 
63             ok[rank[1]] = 1;
64             for(j = 1; j <= r; j++){
65                 ok[rank[1+ j] = 1;
66             }
67             if(res > (w = dj(n + 1)))
68                 res = w;
69         }
70         printf("%d\n", res);
71     }
72     return 0;
73 }

posted on 2008-09-03 23:57 memorygarden 阅读(427) 评论(0)  编辑 收藏 引用 所属分类: 报告

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理