http://acm.hdu.edu.cn/showproblem.php?pid=2962 怪题..................................
最短路径呀，一开始不知道怎么去平衡题意中的两个条件，后来看以人家的解题思路，才知道只要在2分查找它的最大高度，然后在最大高度的条件下，去求其最短路径，以前没怎么用过2分，今天居然用在最短路径中，感觉挺神奇的，呵呵.............
#include<iostream>using namespace std;const int MAX=1001;const int MAXINT=999999999;int map[MAX][MAX][2];int visit[MAX];int dist[MAX];int path[MAX];int n,m,b,e,tall,fist,mid; bool Dijkstra(){ for(int i=1;i<=n;i++) { visit[i]=0; if(map[b][i][0]>=mid) dist[i]=map[b][i][1]; else dist[i]=MAXINT; path[i]=b; } visit[b]=1; int k=-1,min; for(int i=1;i<n;i++) { min=MAXINT; for(int j=1;j<=n;j++) if(!visit[j]&&min>dist[j]&&map[path[j]][j][0]>=mid) { min=dist[j]; k=j; } if(k!=-1) visit[k]=1; else return false; if(k==e) return true; for(int j=1;j<=n;j++) if(!visit[j]&&map[k][j][1]!=MAXINT&&map[k][j][0]>=mid) if(dist[j]>dist[k]+map[k][j][1]) { dist[j]=dist[k]+map[k][j][1]; path[j]=k; } } return false; }int main(){ int T=0; scanf("%d%d",&n,&m); while(1) { if(n==0&&m==0) break; if(T>0) printf("/n"); printf("Case %d:/n",++T); for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) map[i][j][1]=MAXINT; map[i][i][1]=MAXINT; } int x,y,height,length; for(int i=1;i<=m;i++) { scanf("%d%d%d%d",&x,&y,&height,&length); map[x][y][1]=map[y][x][1]=length; if(height==-1) height=MAXINT; map[x][y][0]=map[y][x][0]=height; } scanf("%d%d%d",&b,&e,&tall); fist=1; int ans; mid=(fist+tall)/2; while(fist<=tall) { if(Dijkstra()) { ans=dist[e]; fist=mid+1; } else tall=mid-1; mid=(fist+tall)/2; } if(tall==0) printf("cannot reach destination/n"); else { printf("maximum height = %d/n",tall); printf("length of shortest route = %d/n",ans); } scanf("%d%d",&n,&m); } return 0;}
