5 6 1 2 7 5 1 3 4 2 2 4 -1 10 2 5 2 4 3 4 10 1 4 5 8 5 1 5 10 5 6 1 2 7 5 1 3 4 2 2 4 -1 10 2 5 2 4 3 4 10 1 4 5 8 5 1 5 4 3 1 1 2 -1 100 1 3 10 0 0
Case 1: maximum height = 7 length of shortest route = 20 Case 2: maximum height = 4 length of shortest route = 8 Case 3: cannot reach destination
思路：用Dijkstra的思想来求最大高度，还要再用Dijkstra求最短路。
#include <cstdio>
#include <algorithm>
#define INF 99999999
using namespace std;
int h[1001],d[1001],maph[1001][1001],mapd[1001][1001];
bool vis[1001];
int main()
{
int n,m,i,j,s,e,lim,t,a,b,c,mm,mi,casenum=1;
while(~scanf("%d%d",&n,&m) && n)
{
for(i=1;i<=n;i++) vis[i]=0,h[i]=-1,d[i]=INF;
for(i=1;i<=n;i++) for(j=1;j<=n;j++) maph[i][j]=0,mapd[i][j]=INF;
while(m--)
{
scanf("%d%d%d%d",&a,&b,&c,&t);
mapd[a][b]=mapd[b][a]=t;
if(c!=-1) maph[a][b]=maph[b][a]=c;
else maph[a][b]=maph[b][a]=INF;
}
scanf("%d%d%d",&s,&e,&lim);
t=n-1;
h[s]=lim;
d[s]=0;
while(t--)//用Dijkstra的思想来求最大高度
{
mm=0;
for(i=1;i<=n;i++)
{
if(!vis[i] && h[i]>mm)
{
mm=h[i];
mi=i;
}
}
vis[mi]=1;
if(mi==e) break;
for(i=1;i<=n;i++)
{
if(!vis[i] && mapd[mi][i]<INF)
{
if(h[i]<min(h[mi],maph[mi][i])) h[i]=min(h[mi],maph[mi][i]);
}
}
}
for(i=1;i<=n;i++) vis[i]=0;//求最短距离
t=n-1;
d[s]=0;
while(t--)
{
mm=INF;
for(i=1;i<=n;i++)
{
if(!vis[i] && d[i]<mm)
{
mm=d[i];
mi=i;
}
}
vis[mi]=1;
if(mi==e) break;
for(i=1;i<=n;i++)
{
if(!vis[i] && mapd[mi][i]<INF && maph[mi][i]>=h[e])
{
if(d[i]>d[mi]+mapd[mi][i])
{
d[i]=d[mi]+mapd[mi][i];
}
}
}
}
if(casenum>1) printf("\n");
printf("Case %d:\n",casenum++);
if(d[e]<INF) printf("maximum height = %d\nlength of shortest route = %d\n",h[e],d[e]);
else printf("cannot reach destination\n");
}
}
HDU-2962-Trucking(最短路),布布扣,bubuko.com
原文：http://blog.csdn.net/faithdmc/article/details/24033157