hdu2962 Trucking

#include<stdio.h>

const int MAX=1005;
const int INF=100000000;
int dis[MAX];
struct Graph
{
    int dis,height;
};
Graph g[MAX][MAX];
bool visit[MAX];
int start,end,limit,n;

bool dijkstra()
{
    for(int i=1;i<=n;i++)
        visit[i]=0;

    for(int i=1;i<=n;i++)
    {
        if(g[start][i].height>=limit)
        {
            dis[i]=g[start][i].dis;
        }
        else
            dis[i]=INF;
    }
    visit[start]=1;
    
    while(true)
    {
        int min=INF,v=-1;
        for(int j=1;j<=n;j++)
        {
            if(!visit[j]&&min>dis[j])
            {
                min=dis[j];
                v=j;
            }
        }

        if(v==end) return true;        //存在通路，附带计算出最短路径

        if(v==-1) return false;        //不存在通路


        visit[v]=1;
        for(int j=1;j<=n;j++)        //用新找到最近的点来更新从源点到未到的点的距离

        {
            if(!visit[j]&&g[v][j].height>=limit&&dis[j]>dis[v]+g[v][j].dis)
            {
                dis[j]=dis[v]+g[v][j].dis;
            }
        }
    }
}

int main()
{
    int r,count=0;
    while(scanf("%d%d",&n,&r),n)
    {
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
            {
                g[i][j].dis=INF;
                g[i][j].height=0;
            }

        int v1,v2,c,d;
        while(r--)
        {
            scanf("%d%d%d%d",&v1,&v2,&c,&d);
            g[v1][v2].dis=g[v2][v1].dis=d;
            if(c==-1) c=INF;
            g[v1][v2].height=g[v2][v1].height=c;
        }
        scanf("%d%d%d",&start,&end,&limit);

        int left=1,right=limit,ans=INF;
        while(left<=right)        //循环退出时left=right+1,此时left高度不成立，right高度是最大高度

        {
            limit=(left+right)/2;
            if(dijkstra())        
            {
                ans=dis[end];    //记录最短路径

                left=limit+1;        
            }                    
            else
                right=limit-1;    
        }                            
                                    
        if(count) printf("\n");
        printf("Case %d:\n",++count);
        if(ans==INF)
            printf("cannot reach destination\n");
        else
            printf("maximum height = %d\nlength of shortest route = %d\n",right,ans);
    }
    return 0;
}


总结：

采用二分搜索的方式来枚举最终最大高度，之后来判断在该最大高度下是否存在通路， 若存在通路在计算在该最大高度下的最短路，但可以通过dijkstra算法将枚举之后的这两个判断综合在一起，即通过dijkstra算法能从源点找到终点就调大枚举高度，若不能找到则调小枚举高度，在不断的调整过程中，right值所对应的高度会不断逼近最后一个更新ans值所对应的高度，因而最终right最大高度所对应的最短路径即为ans