程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> HDU 2363 Cycling(二分+枚舉+限制最短路,好題)

HDU 2363 Cycling(二分+枚舉+限制最短路,好題)

編輯:C++入門知識

題目大意:
小明從家裡走到學校去考試, 路上有各個交叉點,它們有自己的海拔高度。 小明從家裡走到學校的路上,必然會經過不同的交叉點,因此會不斷的走上走下,忐忐忑忑,這讓他很不安,會影響他考試的發揮。因此,他要選擇一條起伏最小的路去學校。所謂的“起伏最小”,是指這條路上海拔最高的點與海拔最低的點的差值最小。
在起伏最小的前提下,還要求出路程距離最短。

分析與總結:
這題讓我想起以前做過的一題,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]; 
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; 

 

 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved