设为首页 加入收藏

TOP

HDU 2363 Cycling(一)
2012-11-30 12:25:54 来源: 作者: 【 】 浏览:794
Tags:HDU  2363  Cycling

    题目大意:

    小明从家里走到学校去考试, 路上有各个交叉点,它们有自己的海拔高度。 小明从家里走到学校的路上,必然会经过不同的交叉点,因此会不断的走上走下,忐忐忑忑,这让他很不安,会影响他考试的发挥。因此,他要选择一条起伏最小的路去学校。所谓的"起伏最小",是指这条路上海拔最高的点与海拔最低的点的差值最小。

    在起伏最小的前提下,还要求出路程距离最短。

    分析与总结:

    这题让我想起以前做过的一题,HDU1598 ,不过那时是用最小生成树做的,而且那题只需要输出最小差而不用求最短路。

    这题中,根据高度差的递增,明显满足条件的路径数量也是递增的,因此可以二分"高度差".

    光有"高度差"还是不够的,因为"起伏值"等于最大高度减最小高度, 所以需要再枚举最小高度(下限low), 在根据最小高度+"高度差"得到最大高度(上限up), 有了low和up这两个条件,就可以进行求限制最短路。

    做这题WA了有20+,  因为在求最短路时没有排除掉超过"上限"的边。

    之后试着最小生成树的方法做了下,先求出"最小差"和上限与下限,然后再求最短路,但是WA了,纠结中…

    代码:

    二分+枚举+最短路

    [cpp]

    #include<iostream>

    #include<cstdio>

    #include<cstring>

    #include<queue>

    #include<algorithm>

    using namespace std;

    const int INF = 0x7fffffff;

    const int VN  = 120;

    const int EN  = 10005;

    int n;

    int m;

    int size;

    int head[VN];

    int h[VN];

    int order[VN];

    int d[VN];

   

首页 上一页 1 2 3 下一页 尾页 1/3/3
】【打印繁体】【投稿】【收藏】 【推荐】【举报】【评论】 【关闭】 【返回顶部
分享到: 
上一篇HDU 1690 Bus Sys.. 下一篇C++强制类型转换操作结果的总结

评论

帐  号: 密码: (新用户注册)
验 证 码:
表  情:
内  容: