hdu 2962(最短路+二分）

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2962
思路：二分枚举高度，每次都sfpa一下，然后如果dist[e]存在的话，就更新shortpath...
View Code
 1 #include<iostream>
 2 #include<cstdio>
 3 #include<queue>
 4 #include<vector>
 5 #include<algorithm>
 6 const int MAXN=1000+10;
 7 const int inf=1<<30;
 8 using namespace std;
 9 struct Node{
10     int v,w,h;
11 };
12 vector<Node>mp[MAXN];
13 int n,m;
14 int s,e;
15 int dist[MAXN];
16 bool visited[MAXN];
17 
18 void SPFA(int u,int limit){
19     for(int i=1;i<=n;i++)dist[i]=inf;
20     dist[u]=0;
21     memset(visited,false,sizeof(visited));
22     queue<int>Q;
23     Q.push(u);
24     while(!Q.empty()){
25         int u=Q.front();
26         Q.pop();
27         visited[u]=false;
28         for(int i=0;i<mp[u].size();i++){
29             int v=mp[u][i].v;
30             int h=mp[u][i].h;
31             int w=mp[u][i].w;
32             if(h<limit)continue;//h应该尽量要大
33             if(dist[u]+w<dist[v]){
34                 dist[v]=dist[u]+w;
35                 if(!visited[v]){
36                     Q.push(v);
37                     visited[v]=true;
38                 }
39             }
40         }
41     }
42 }
43 
44 
45 
46 int main(){
47     int _case=1;
48     while(~scanf("%d%d",&n,&m)&&(n+m)){
49         if(_case>1)puts("");
50         for(int i=1;i<=n;i++)mp[i].clear();
51         for(int i=1;i<=m;i++){
52             int u,v,w,h;
53             scanf("%d%d%d%d",&u,&v,&h,&w);
54             Node p1,p2;
55             p1.v=u,p2.v=v;
56             p1.w=p2.w=w;
57             if(h==-1)h=inf;
58             p1.h=p2.h=h;
59             mp[u].push_back(p2);
60             mp[v].push_back(p1);
61         }
62         int limit;
63         scanf("%d%d%d",&s,&e,&limit);
64         //二分的时候得注意了，不知为什么wa了好多次
65         int low=0,high=limit,res=inf;
66         while(low<high){
67             int mid=(low+high+1)>>1;
68             SPFA(s,mid);
69             if(dist[e]==inf){
70                 high=mid-1;
71             }else {
72                 low=mid;
73                 res=dist[e];
74             }
75         }
76         printf("Case %d:\n",_case++);
77         if(res==inf){
78             printf("cannot reach destination\n");
79         }else {
80             printf("maximum height = %d\n",low);
81             printf("length of shortest route = %d\n",res);
82         }
83     }
84     return 0;
85 }