题目链接：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[];
int head[],dis[],vis[];
queue<int>q;
int start,end1,limit,min1,max1;
int n,m,k,t,cnt;
void init()
{
memset(head,-,sizeof(head));
cnt=;
}
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=;i<=n;i++)
dis[i]=INF;
memset(vis,,sizeof(vis));
q.push(start);
vis[start]=;
dis[start]=;
while(!q.empty())
{
int u=q.front();
q.pop();
vis[u]=;
for(int i=head[u];i!=-;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]=;
q.push(v);
}
}
}
}
}
void two_(int l,int r,int start,int end1)
{
int mid;
max1=-,min1=-;
while(l<=r)
{
mid=(l+r)/;
BFS(start,end1,mid);
if(dis[end1]!=INF) //可以到达
{
l=mid+;
max1=mid; //更新
min1=dis[end1];
}
else
{
r=mid-;
}
}
}
int main()
{
int count1=;
while(scanf("%d%d",&n,&m)!=EOF)
{
if(!n||!m)
break;
init();
int u,v,w,h;
for(int i=;i<m;i++)
{
scanf("%d%d%d%d",&u,&v,&h,&w);
if(h==-)
h=INF;
add(u,v,w,h);
add(v,u,w,h);
}
scanf("%d%d%d",&start,&end1,&limit);
two_(,limit,start,end1); //二分找答案
if(count1>)
printf("\n");
printf("Case %d:\n",++count1);
if(min1==-||max1==-)
printf("cannot reach destination\n");
else
{
printf("maximum height = %d\n",max1);
printf("length of shortest route = %d\n",min1);
}
}
return ;
}