二分+最短路 UVALive

题目链接：https://vjudge.net/contest/244167#problem/E

这题做了好久都还是超时，看了博客才发现可以用二分+最短路（dijkstra和spfa都可以），也可以用dijikstra先算一遍可以求的最大高度，再用dijkstra算一遍这个高度下的最短路，这个应该快一点。

题意：第一行输入n，m表示n个点，m条边，接下来m行，每行有四个数字u，v，h，w，其中u，v表示这条边连接的两个城市，h表示在这条边上货车可以通过的最大高度，w表示距离，最后一行输入三个数字start，end，limit分别表示起点，终点，卡车可以载的最大高度。现在叫我们求出卡车从起点到终点可以载的最大高度下的最短路。就是先保证高度最大，再保证距离最短。

思路：用二分来假设假设高度，再用最短路判断从起点能否到终点，同时求出最短路。

之所以写这篇博客是要告诉大家，在这里有格式要求，经过我一个小时的摸索发现如果在格式错误的情况下在UVA提交会显示WA而不是PE

如果大家是答案错误又找不出问题，可以看看格式是否正确。

代码：

#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
#include<map>
#include<stack>
#include<cmath>
#include<vector>
#include<fstream>
#include<set>
#include<cstdio>
using namespace std;
#define eps 1e-8
#define ll long long
#define INF 0x3fffffff
struct node{
    int v,next,w,h;
}edge[1000020];
int head[1010],dis[1010],vis[1010];
queue<int>q;
int start,end1,limit,min1,max1;
int n,m,k,t,cnt;
void init()
{
    memset(head,-1,sizeof(head));
    cnt=0;
}
void add(int u,int v,int w,int h)
{
    edge[++cnt].v=v;
    edge[cnt].w=w;
    edge[cnt].h=h;
    edge[cnt].next=head[u];
    head[u]=cnt;
}
void BFS(int start,int end1,int mid)
{
    while(!q.empty())
    q.pop();
    for(int i=1;i<=n;i++)
    dis[i]=INF;
    memset(vis,0,sizeof(vis));
    q.push(start);
    vis[start]=1;
    dis[start]=0;
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        vis[u]=0;
        for(int i=head[u];i!=-1;i=edge[i].next)
        {
            int v=edge[i].v;
            int w=edge[i].w;
            int h=edge[i].h;
            if(h>=mid&&dis[v]>dis[u]+w)
            {
                dis[v]=dis[u]+w;
                if(!vis[v])
                {
                    vis[v]=1;
                    q.push(v);
                }
            }
        }
    }
}
void two_(int l,int r,int start,int end1)
{
    int mid;
    max1=-1,min1=-1;
    while(l<=r)
    {
        mid=(l+r)/2;
        BFS(start,end1,mid);
        if(dis[end1]!=INF)    //可以到达 
        {
            l=mid+1;
            max1=mid;        //更新 
            min1=dis[end1];
        }
        else
        {
            r=mid-1;
        }
    }
}
int main()
{
    int count1=0;
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        if(!n||!m)
        break;
        init();
        int u,v,w,h;
        for(int i=0;i<m;i++)
        {
            scanf("%d%d%d%d",&u,&v,&h,&w);
            if(h==-1)
            h=INF;
            add(u,v,w,h);
            add(v,u,w,h);
        }
        scanf("%d%d%d",&start,&end1,&limit);
        two_(0,limit,start,end1);    //二分找答案 
        if(count1>0)
        printf("
");
        printf("Case %d:
",++count1);
        if(min1==-1||max1==-1)
        printf("cannot reach destination
");
        else
        {
            printf("maximum height = %d
",max1);
            printf("length of shortest route = %d
",min1);
        }
    }
    return 0;
}