hdu2962 Trucking (最短路+二分查找)

#include <iostream>
#include <cstdio>
#include <queue>
#include <cstring>
using namespace std;

struct node
{
    int h,len;
} map[1010][1010];

int start,end,height,c;
int node[1010];
const int inf=9999999;

int Spfa(int high)
{
    for (int i=1;i<=c;i++)
    node[i]=inf;
    queue<int>q;
    int inq[1010]= {0};
    int tm=start;
    node[tm]=0;
    inq[tm]=1;
    q.push(tm);
    while (!q.empty())
    {
        int s=q.front();
        q.pop();
        for (int i=1; i<=c; i++)
        {
            //cout<<s<<i<<" "<<node[i]<<" "<<map[s][i].len<<endl;
            if (map[s][i].h>=high&&node[i]>map[s][i].len+node[s])
            {
                node[i]=map[s][i].len+node[s];
                //cout<<"   "<<i<<" "<<node[i]<<endl;
                if (!inq[i])
                {
                    q.push(i);
                    inq[i]=1;
                }
            }
        }
        inq[s]=0;

    }
    if (node[end]!=inf)
        return node[end];
    else
        return -1;
}

int main ()
{
    int r,maxx,minn,h,k=1;
    while (cin>>c>>r&&(c||r))
    {
        int ans=-1,cmp=-1;
        for(int i=1;i<=c;i++)
        {
            for(int j=1;j<=c;j++)
            {
                map[i][j].len=inf;
                map[i][j].h=0;
            }
        }
        maxx=0,minn=inf;
        for (int i=1; i<=r; i++)
        {
            int a,b,len;

            cin>>a>>b>>h>>len;
            if(h==-1) h=inf;
            if (minn>h) minn=h;
            if (maxx<h) maxx=h;
            //cout<<minn<<" "<<maxx<<endl;
            if (map[a][b].len>len)
                map[a][b].len=map[b][a].len=len;
            if (map[a][b].h<h)
                map[a][b].h=map[b][a].h=h;
        }
        cin>>start>>end>>height;
        maxx=height>maxx?maxx:height;
        int l=minn,r=maxx;
        while (l<=r)
        {
            int mid=(r+l)>>1;
            //cout<<l<<" "<<r<<" "<<mid<<endl;
            int flag=Spfa(mid);
            if (flag!=-1)
            {
                l=mid+1;
                ans=mid;
                cmp=flag;
            }
            else
                r=mid-1;
        }
        if(k>1)
        printf("\n");
        printf("Case %d:\n",k++);
        if(ans==-1)
        printf("cannot reach destination\n");
        else
        {
            printf ("maximum height = %d\n",ans);
        printf ("length of shortest route = %d\n",cmp);
        }
    }
    return 0;
}