原题链接：http://acm.hdu.edu.cn/showproblem.php?pid=2962
分析：最短路+二分。
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<cmath> 5 #include<string> 6 #include<algorithm> 7 #include<vector> 8 #include<queue> 9 #include<map> 10 #define ll long long 11 #define inf 1000000000 12 #define maxn 1005 13 using namespace std; 14 struct edge 15 { 16 int to,h,len; 17 edge(int x,int y,int z) 18 { 19 to=x;h=y;len=z; 20 } 21 }; 22 vector<edge>e[maxn]; 23 queue<int>q; 24 bool vis[maxn]; 25 int d[maxn],n,m,s,t,H,maxh; 26 void spfa(const int s,int h) 27 { 28 while(!q.empty())q.pop(); 29 for(int i=0;i<=n;i++) 30 { 31 d[i]=inf;vis[i]=false; 32 } 33 d[s]=0;vis[s]=true; 34 q.push(s); 35 while(!q.empty()) 36 { 37 int u=q.front();q.pop(); 38 for(int i=0;i<e[u].size();i++) 39 { 40 if(e[u][i].h>=h&&d[e[u][i].to]>d[u]+e[u][i].len) 41 { 42 d[e[u][i].to]=d[u]+e[u][i].len; 43 if(!vis[e[u][i].to]) 44 { 45 vis[e[u][i].to]=true; 46 q.push(e[u][i].to); 47 } 48 } 49 } 50 vis[u]=false; 51 } 52 } 53 int main() 54 { 55 int cas=1; 56 while(~scanf("%d%d",&n,&m)) 57 { 58 if(n==0&&m==0)break; 59 for(int i=0;i<maxn;i++)e[i].clear(); 60 int u,v,h,l; 61 for(int i=0;i<m;i++) 62 { 63 scanf("%d%d%d%d",&u,&v,&h,&l); 64 if(h==-1)h=inf; 65 e[u].push_back(edge(v,h,l)); 66 e[v].push_back(edge(u,h,l)); 67 } 68 scanf("%d%d%d",&s,&t,&H); 69 int lef=1,r=H,maxh=0,ans=inf; 70 while(lef<=r) 71 { 72 int mid=(r+lef)>>1; 73 if(mid<=0)break; 74 spfa(s,mid); 75 if(d[t]!=inf) 76 { 77 lef=mid+1; 78 maxh=mid; 79 ans=d[t]; 80 } 81 else r=mid-1; 82 } 83 if(cas>1) puts(""); 84 printf("Case %d: ",cas++); 85 if(ans==inf||maxh<1)cout<<"cannot reach destination "; 86 else { 87 printf("maximum height = %d ",maxh); 88 printf("length of shortest route = %d ",ans); 89 } 90 } 91 return 0; 92 }