pku 1062

2009年7月24日

题目链接：PKU 1062 昂贵的聘礼

分类：最短路

题目分析与算法原型
        这道题目其实就是一个最短路径，不过是增加了等级限制，可以这样考虑，增加一个节点n+1对应第n+1件物品，对于前面1到n每一个物品，增加一条其到第n+1个物品的边，该边的权值为该物品的原来价格，对于题目给定的输入数据，若物品x,能用物品y换的一个优惠价格p,则增加一条从x到y的边，其权值为p,这样一来，就构好图了，问题就转换成了求从节点1到节点n+1的最短路径问题了，当然了，该题目还有一个等级限制，所以在运用Dijkastra的时候，应该注意当前的路径中最大等级和最小等级间的差是否超过了给定的m，若超过了，则当前的路径就不行了，具体处理方法可以设置两个变量_min,_max分别存的是路径中最小和最大的等级，然后每当要加入节点时判断是否满足，对于不满足的点，标记位仍然置为1，但是下面的操作就Continue略过就行了。

Code:

 1#include<stdio.h>
 2#include<string.h>
 3#define max 0x7fffffff
 4#define len 110
 5
 6int m,n,p,l,x,map[len][len],i,j,t,v,dis[len],flag[len],dj[len],min,u;
 7int _min,_max;
 8
 9void init()
10{
11    for(i=1;i<=n;i++)
12        for(j=1;j<=n;j++)
13        {
14            if(i==j)map[i][j]=0;
15            else map[i][j]=max;
16        }
17}
18
19void dij()
20{
21    int xiao,da,go;
22    for(i=1;i<=n+1;i++)dis[i]=map[1][i];
23    flag[1]=1;
24
25    for(i=1;i<=n;i++)
26    {
27        min=max;
28        go=0;
29        for(j=1;j<=n+1;j++)
30            if(flag[j]==0&&dis[j]<min)
31            {
32                u=j;
33                min=dis[j];
34            }
35        flag[u]=1;
36        if(dj[u]<_min)
37        {
38            xiao=_min;
39            _min=dj[u];
40            if(_max-_min>m)
41            {
42                go=1;
43                _min=xiao;
44            }
45        }
46        else if(dj[u]>_max)
47        {
48            da=_max;
49            _max=dj[u];
50            if(_max-_min>m)
51            {
52                go=1;
53                _max=da;
54            }
55        }
56        if(go)continue;
57        for(j=1;j<=n+1;j++)
58            if(flag[j]==0&&map[u][j]<max&&dis[u]+map[u][j]<dis[j])
59                dis[j]=dis[u]+map[u][j];
60    }
61    
62}
63
64int main()
65{
66    while(scanf("%d%d",&m,&n)!=EOF)
67    {
68        init();
69        memset(flag,0,sizeof(flag));
70        for(i=1;i<=n;i++)
71        {
72            scanf("%d%d%d",&p,&l,&x);
73            map[i][n+1]=p;
74            dj[i]=l;
75            for(j=1;j<=x;j++)
76            {
77                scanf("%d%d",&t,&v);
78                map[i][t]=v;
79            }
80        }
81        _max=dj[1];
82        _min=dj[1];
83        dij();
84        printf("%d\n",dis[n+1]);
85    }
86    return 0;
87}
88
89

posted on 2009-07-24 19:30 蜗牛也Coding 阅读(742) 评论(4)  编辑 收藏 引用

评论

# re: pku 1062 2009-09-12 16:36 姓李

在下有疑问，如果有一个点，第一次被选择之后，发现其不符等级限制，那么就不更新了，可是有没有可能最小的价钱是要经过这个点呢？
例如下面的数据
1 5
10000 3 2
2 8000
3 8000
3000 4 1
4 400
3000 2 1
4 500
1000 3 1
5 100
100 2 0

难道结果不是5700吗？
不懂啊，如果有空帮忙解释一下，我的邮箱lijh_402@yeah.net  回复  更多评论   

# re: pku 1062 2009-10-01 22:44 JustCodeIT

我也不太懂楼主的算法原理，为什么你不用枚举呢？
同楼上的疑问？  回复  更多评论   

# re: pku 1062 2010-07-20 14:52 walker01

增加一个节点n+1, 妙！  回复  更多评论   

# re: pku 1062 2011-06-23 11:09 Firefrog

楼主的代码虽然可以AC，但是是错的。
你试一下这个数据：
1 4
10000 3 2
2 1
3 3
1000 2 2
4 1
3 1
1000 3 1
4 2
100 4 0
正确答案应该是：
105
楼主的代码输出的是 1001。  回复  更多评论   


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


<2009年7月>
日一二三四五六
2829301234
567891011
12131415161718
19202122232425
2627282930311
2345678

导航

统计

常用链接

留言簿(8)

随笔档案(78)

搜索

积分与排名

最新评论

阅读排行榜

评论排行榜