這道題實際上就是最短路，只不過增加了高度這個限制條件，由于時間限制是10s,我們不妨二分枚舉出所有高度在1-limit之間的情況（時間復(fù)雜度是n^2log n，可以接受）取最大的即可。
PS:本人覺得此題最BT之處在于輸出格式,Fuck！最后一個Case居然不要空行，害我PE十幾次。
#include<iostream>
#include<cmath>
#include<cstdio>
#include<algorithm>
using namespace std;
#define MAX 1001
#define MAX_INTEGER 0x7fffffff
int n,m;
int graph[MAX][MAX];
int copygraph[MAX][MAX];
int graphheight[MAX][MAX];
bool visit[MAX];
int dis[MAX];
int s,t,lim;
int maxn;
int shortestpath;
int casenum;
bool dijkstra(int s,int t,int graph[MAX][MAX])
{
memset(visit,false,sizeof(visit));
int i;
int j;
for(i=1;i<=n;i++)
{
dis[i]=graph[s][i];
}
graph[s][s]=0;
dis[s]=0;
visit[s]=true;
for(i=1;i<n;i++)
{
int mark_num=n;
int mark_dis=MAX_INTEGER;
int temp=MAX_INTEGER;
for(j=1;j<=n;j++)
{
if(!visit[j]&&dis[j]<temp)
{
mark_num=j;
temp=dis[j];
}
}
if(temp==MAX_INTEGER)
return false;
visit[mark_num]=true;
if(mark_num==t)
return true;
for(j=1;j<=n;j++)
{
if((!visit[j])&&(graph[mark_num][j]<MAX_INTEGER))
{
int newdis=dis[mark_num]+graph[mark_num][j];
if(newdis<dis[j])
{
dis[j]=newdis;
}
}
}
}
return false;
}
int main ()
{
// FILE *in,*out;
// in = fopen("trucking.in", "r");
// out = fopen("out.txt","w");
int i,j;
casenum=0;
while(scanf("%d%d",&n,&m))
{
casenum++;
maxn=0;
if(n==0&&m==0)
break;
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
if(i==j)
graph[i][j]=0;
else
graph[i][j]=MAX_INTEGER;
}
}
for(i=1;i<=m;i++)
{
int a,b,height,len;
scanf("%d%d%d%d",&a,&b,&height,&len);
graph[a][b]=len;
graph[b][a]=len;
if(height==-1)
{
graphheight[a][b]=9999999;
graphheight[b][a]=9999999;
}
else
{
graphheight[a][b]=height;
graphheight[b][a]=height;
}
}
scanf("%d%d%d",&s,&t,&lim);
int l=1;
int r=lim;
while(l<=r)
{
int mid=(r+l)>>1;
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
copygraph[i][j]=graph[i][j];
if(graphheight[i][j]<mid&&i!=j)
copygraph[i][j]=MAX_INTEGER;
}
}
if(dijkstra(s,t,copygraph)==false)
{
r=--mid;
continue;
}
else
{
l=mid+1;
maxn=mid;
shortestpath=dis[t];
continue;
}
}
if(casenum>1)
printf("\n");
if(maxn==0)
printf("Case %d:\ncannot reach destination\n",casenum);
else
printf("Case %d:\nmaximum height = %d\nlength of shortest route = %d\n",casenum,maxn,shortestpath);
}
return 0;
}