题目大意：给你城市数c，道路数r，运载车的限高h，以及每条道路的限高limit，让你求start到end的货物的最大高度res（res<=limit,res<=h）,和在货物最大高度下，从start到end的最短路。
大体思路：二分答案（res∈[1.h]），然后再求最大高度下的最短路即可。具体看代码。
#include <queue> #include <string.h> #include <string> #include <vector> using namespace std; const int inf=0x3f3f3f3f; const int maxn=1005; struct edge{ int to; int cost; int height; edge(int _to=0,int _cost=0,int _height=0):to(_to),cost(_cost),height(_height){} }; int n,m; vector<edge> es[maxn]; void addedge(int u,int v,int w,int h) { es[u].push_back(edge(v,w,h)); } bool vis[maxn]; int cnt[maxn],dis[maxn]; void spfa(int s,int limit) { memset(vis,false,sizeof(vis)); memset(cnt,0,sizeof(cnt)); for(int i=1;i<=n;i++) dis[i]=inf; for(int i=0;i<es[s].size();i++) if(es[s][i].height<limit) dis[es[s][i].to]=inf;//道路的最大高度小于货物最大高度，即车辆不能走这条道路，那么令dis[i]=∞； vis[s]=true; dis[s]=0; queue<int> que; while(!que.empty()) que.pop(); que.push(s); cnt[s]=1; while(!que.empty()) { int u=que.front(); que.pop(); vis[u]=false; for(int i=0;i<es[u].size();i++) { int v=es[u][i].to; if(dis[v]>dis[u]+es[u][i].cost&&es[u][i].height>=limit)//不满足条件就不能选择这条边 { dis[v]=dis[u]+es[u][i].cost; if(!vis[v]) { vis[v]=true; que.push(v); if(++cnt[v]>n) break; //记录入队次数，判断负环的存在 } } } } /*return true;*/ } int main() { /*freopen("1.txt","r",stdin); */ int kase=1; while(scanf("%d%d",&n,&m)!=EOF) { for(int i=0;i<maxn;i++) es[i]=vector<edge>(0);//vector 数组清零，坑点。 if(n==0&&m==0) break; if(kase!=1) printf("\n"); for(int i=0;i<m;i++) { int u,v,h,l; scanf("%d%d%d%d",&u,&v,&h,&l); if(h==-1) h=inf; addedge(u,v,l,h); addedge(v,u,l,h); } int start,end,limit; scanf("%d %d %d",&start,&end,&limit); int left=1,right=limit,ans=inf,res=0; while(left<=right) { int mid=(left+right)/2; spfa(start,mid); int temp=dis[end]; if(temp!=inf) { left=mid+1; ans=temp; res=mid; } else{ right=mid-1; } } printf("Case %d:\n",kase++); if(ans==inf) printf("cannot reach destination\n"); else{ printf("maximum height = %d\n",res); printf("length of shortest route = %d\n",ans); } } return 0; }