HDU 2363 Cycling：二分+枚举+限制最短路，好题

HDU 2363 Cycling：二分+枚举+限制最短路，好题2014-12-02链接：

http://acm.hdu.edu.cn/showproblem.php？pid=2363

题目大意：

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

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

分析与总结：

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

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

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

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

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

代码：

二分+枚举+最短路

#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];int up;// 上界int low; // 下界bool inq[VN];struct Edge{int v,next;int w;}E[EN];void addEdge（int u,int v,int w）{E[size].v=v;E[size].w=w;E[size].next=head[u];head[u]=size++;}int SPFA（int src）{memset（inq, 0, sizeof（inq））;for（int i=0; i<=n; ++i）d[i]=INF;d[src]=0;if（h[src]<low || h[src]>up） return INF;// 起点不符合条件直接返回INFqueue<int>q;q.push（src）;while（！q.empty（））{int u=q.front（）;q.pop（）;if（h[u]<low || h[u]>up） continue;// 排除符合和限制的inq[u] = false;for（int e=head[u]; e！=-1; e=E[e].next）if（h[E[e].v]>=low&&h[E[e].v]<=up）{//有限制int tmp=d[u]+E[e].w;if（d[E[e].v] > tmp）{d[E[e].v] = tmp;if（！inq[E[e].v]）{inq[E[e].v]=true;q.push（E[e].v）;}}}}return d[n];}int main（）{int T, u, v;int len, Min, Max;scanf（"%d",&T）;while（T--）{scanf（"%d%d",&n,&m）;size=0;memset（head, -1, sizeof（head））;for（int i=1; i<=n; ++i）{scanf（"%d", &h[i]）;order[i]=h[i];if（h[i]<Min）Min=h[i];if（h[i]>Max）Max=h[i];}for（int i=0; i<m; ++i）{scanf（"%d%d%d",&u,&v,&len）;addEdge（u,v,len）;addEdge（v,u,len）;} sort（order+1, order+1+n）;int left=0, right=Max-Min+1, mid;int ans, dif=INF, minlen=INF;while（left < right）{ // 二分“高度差”mid = （left+right）>>1;bool flag=false;for（int i=1; i<=n; ++i）{ // 枚举最低海拔low=order[i];up=order[i]+mid; // 得到海拔上限int tmp=SPFA（1）;if（tmp！=INF）{flag=true;ans=tmp;break;}} if（flag）{right=mid;if（mid<dif）{dif=mid;minlen=ans;}else if（mid==dif && ans<minlen）{minlen=ans;}}else{left=mid+1;} }printf（"%d %d
", dif, minlen）;}return 0;}

作者：csdn博客 shuangde800