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

链接：

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;  // 起点不符合条件直接返回INF
    queue<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\n", dif, minlen);
    }
    return 0;
}

—— 生命的意义，在于赋予它意义。

    
  原创http://blog.csdn.net/shuangde800，By  D_Double (转载请标明)