昂贵的聘礼--POJ1062

昂贵的聘礼

Time Limit : 2000/1000ms (Java/Other) Memory Limit : 20000/10000K (Java/Other)

Total Submission(s) : 14 Accepted Submission(s) : 3

Problem Description

年轻的探险家来到了一个印第安部落里。在那里他和酋长的女儿相爱了，于是便向酋长去求亲。酋长要他用10000个金币作为聘礼才答应把女儿嫁给他。探险家拿不出这么多金币，便请求酋长降低要求。酋长说："嗯，如果你能够替我弄到大祭司的皮袄，我可以只要8000金币。如果你能够弄来他的水晶球，那么只要5000金币就行了。"探险家就跑到大祭司那里，向他要求皮袄或水晶球，大祭司要他用金币来换，或者替他弄来其他的东西，他可以降低价格。探险家于是又跑到其他地方，其他人也提出了类似的要求，或者直接用金币换，或者找到其他东西就可以降低价格。不过探险家没必要用多样东西去换一样东西，因为不会得到更低的价格。探险家现在很需要你的帮忙，让他用最少的金币娶到自己的心上人。另外他要告诉你的是，在这个部落里，等级观念十分森严。地位差距超过一定限制的两个人之间不会进行任何形式的直接接触，包括交易。他是一个外来人，所以可以不受这些限制。但是如果他和某个地位较低的人进行了交易，地位较高的的人不会再和他交易，他们认为这样等于是间接接触，反过来也一样。因此你需要在考虑所有的情况以后给他提供一个最好的方案。
为了方便起见，我们把所有的物品从1开始进行编号，酋长的允诺也看作一个物品，并且编号总是1。每个物品都有对应的价格P，主人的地位等级L，以及一系列的替代品Ti和该替代品所对应的"优惠"Vi。如果两人地位等级差距超过了M，就不能"间接交易"。你必须根据这些数据来计算出探险家最少需要多少金币才能娶到酋长的女儿。

Input

输入第一行是两个整数M，N（1 <= N <= 100），依次表示地位等级差距限制和物品的总数。接下来按照编号从小到大依次给出了N个物品的描述。每个物品的描述开头是三个非负整数P、L、X（X < N），依次表示该物品的价格、主人的地位等级和替代品总数。接下来X行每行包括两个整数T和V，分别表示替代品的编号和"优惠价格"。

Output

输出最少需要的金币数。

Sample Input

1 4

10000 3 2

2 8000

3 5000

1000 2 1

4 200

3000 2 1

4 200

50 2 0

Sample Output

5250

思路：单源最短路径Dijkstra算法，经典算法，和prime算法极为相似，将图中的点分成两个集合，A和B，起初A里面只包含源点S，B中是剩余的点，核心思想是：1，将B中与满足条件的点加入到A中（满足条件的点对于prime算法来说是B中与集合A距离最短的点，对于Dijksttra算法来说是B中到源点S距离最短的点。），记为P，并把P从B中去掉。2，更新：更新B中所有点到集合A（或源点S）的最近距离，每找到一个P就执行一次。循环执行1，2步骤，直到找不到满足条件的P点才结束。由于在P之前的加入到A 中的点都已将B 中的点更新过，因此只有刚加进来的P点才有可能更新B中点到A的最短距离，所有只需要对P点就行考察就行。

对于本题而言，关键点在于如何建图，另外由于有等级差距限制，需要枚举所有可能的等级。

数据结构：点较少时用邻接矩阵，数据较大时使用链式前向星。

 1 int map[MAX][MAX],vis[MAX],dist[MAX];
 2 memset(vis,0,sizeof(vis));
 3 void Dijkstra()　　　　　　　　　　//求单源最短路径；
 4 {
 5     for(i = 1;i <= n;i ++)
 6     {
 7         min = 1 << 30;
 8         k = 0;
 9         for(j = 1;i <= n;j ++)
10         {
11             if(!vis[j] && min > dist[j])
12             {
13                 min = dist[j];
14                 k = j;
15             }
16         }
17         if(k == 0)
18             return ;
19         vis[k] = 1;
20         for(j = 1;j <= n;j ++)
21         {
22             if(!vis[j] && dist[j] > dist[k]+map[k][j])
23                 dist[j] = dist[k]+map[k][j];
24         }
25     }
26     return ;
27 }//End of function;
28 
29 void prime()　　　　　　　　//求最小生成树；
30 {
31     for(i = 1;i <= n;i ++)
32     {
33         min = 1 << 30;
34         k = 0;
35         for(j =1;j <=n;j ++)
36         {
37             if(!vis[j] && min > dist[j])
38             {
39                 min = dist[j];
40                 k = j;
41             }
42         }
43         if(k == 0)
44             return ;
45         vis[k] = 1;
46         for(j = 1;j <= n;j ++)
47         {
48             if(!vis[j] && dist[j] > map[k][j])
49                 dist[j] = map[k][j];
50         }
51     }
52     return ;
53 }//End of function;

AC代码：

 1 #include<stdio.h>
 2 #include<stdlib.h>
 3 #include<string.h>
 4 int dist[105],map[105][105];
 5 int vis[105],rank[105],n,m;
 6 void init1()
 7 {
 8     int i,j;
 9     for(i = 1;i <= n+1;i ++)
10     {
11         for(j = 1;j <= n+1;j ++)
12         {
13             map[i][j] = 1 << 30;
14         }
15     }
16     return ;
17 }
18 
19 void init2()
20 {
21     int i;
22     for(i = 1;i <= n+1;i ++)
23         dist[i] = map[n+1][i];
24     return ;
25 }
26 
27 void Dijkstra(int r)
28 {
29     int i,j,k,min;
30     for(i = 1;i <= n;i ++)
31     {
32         if((rank[i]-r) < -m || (rank[i]-r) > m || rank[i] < r)
33             vis[i] = 1;
34     }
35     for(i = 1;i <= n;i ++)
36     {
37         min = 1 << 30;
38         k = -1;
39         vis[n+1] = 1;
40         for(j = 1;j <= n+1;j ++)
41         {
42             if(!vis[j] && min > dist[j])
43             {
44                 min = dist[j];
45                 k = j;
46             }
47         }
48         if(k == -1)
49             return ;
50         vis[k] = 1;
51         for(j = 1;j <= n;j ++)
52         {
53             if(!vis[j] && dist[j] > dist[k]+map[k][j])
54                 dist[j] = dist[k]+map[k][j];
55         }
56     }
57     return ;
58 }
59 
60 int main(void)
61 {
62     int i,sum;
63     int p,l,x,t,v;
64     //freopen("in.c","r",stdin);
65     //freopen("re.c","w",stdout);
66     while(~scanf("%d%d",&m,&n))
67     {
68         init1();
69         sum = 1 << 30;
70         for(i = 1;i <= n;i ++)
71         {
72              scanf("%d%d%d",&p,&l,&x);
73              map[n+1][i] = p;
74              rank[i] = l;
75              while(x--)
76              {
77                  scanf("%d%d",&t,&v);
78                  map[t][i] = v;
79              }
80         }
81         for(i = rank[1]-m;i <= rank[1]+m;i ++)
82         {
83             init2();
84             memset(vis,0,sizeof(vis));
85             Dijkstra(i);
86             if(sum > dist[1])
87                 sum = dist[1];
88         }
89         printf("%d
",sum);
90     }
91     return 0;
92 }