hdu2962(最短路+二分)

hdu2962(最短路+二分)

題意：在最大的高度下面求最短路，由於題目給出限高，所以我們只需要二分高度然後用SPFA

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
#define N 205
#define maxn 2005
const int INF = 9999999;
int ht[maxn][maxn];
int mp[maxn][maxn];
int d[maxn];
int mid_ht;
int n,m;
int used[maxn];

void SPFA(int s)
{
    fill(d,d+n+1,INF);
    queue que;
    fill(used,used+n+1,0);
    d[s] = 0;
    que.push(s);
    while(!que.empty())
    {
        int u = que.front();que.pop();
        used[u] = 0;
        for(int i = 1; i <= n; i++)
        {
            if(ht[u][i] >= mid_ht && ht[u][i]|| ht[u][i] == -1)
            {
               if(d[i] > d[u] + mp[u][i])
               {
                   d[i] = d[u] + mp[u][i];
                   if(!used[i])
                   {
                       used[i] = 1;
                       que.push(i);
                   }

               }
            }
        }
    }

}


int main()
{
    #ifdef xxz
    freopen("in.txt","r",stdin);
    #endif // xxz
    int a,b,c,e;
    int Case = 1;
    while(~scanf("%d%d",&n,&m))
    {
        if(n == 0 && m== 0) break;
        for(int i = 0; i <= n; i++)
        {
            fill(mp[i],mp[i]+n+1,INF);
            fill(ht[i],ht[i]+n+1,0);
        }

        for(int i = 0; i < m; i++)
        {
            scanf("%d%d%d%d",&a,&b,&c,&e);
            mp[a][b] = mp[b][a] = e;
            ht[a][b] = ht[b][a] = c;
        }

        int start,End,h;
        scanf("%d%d%d",&start,&End,&h);
        int l = 0, r = h;
        int ans = 0 ,ans2 = INF;

        while(l <= r)
        {
            mid_ht = (l+r)/2;
            SPFA(start);
            if(d[End] == INF)
            {
                r = mid_ht - 1;
            }
            else {
                if(ans < mid_ht)
                {
                    ans = mid_ht;
                    ans2 = d[End];
                }
                else if(ans == mid_ht && d[End] < ans2)//注意這一項，當高度相同時考慮更小的路徑
                {
                    ans2 = d[End];
                }
                l = mid_ht+1;
            }
        }
        if(Case >1 ) printf("\n");//不然會PE
        printf("Case %d:\n",Case++);
        if(ans2 == INF || ans == 0)
        {

            printf("cannot reach destination\n");
        }
        else {

            printf("maximum height = %d\n",ans);
            printf("length of shortest route = %d\n",ans2);
        }


    }
    return 0;
}