hdu 3143 Speedy Escape 二分+搜索

PS. 训练赛的时候看完题就想到做法了，写完之后自觉很对，但是无限WA，实在无解，赛后重写一遍，继续无限WA，换G++交，神奇的过了，（改%lf和%f，C++都过不了）唉，无法理解啊。

英文很长，但很简单，题意不赘述了。

首先求到兄弟到所有点的最短路（不能经过警察局），然后求到警察到所有点的最短路。

然后二分速度，dfs验证可行性，若到达当前点的时间小于等于警察到这个点的时间，则可以扩展。（由于是double，所以小于或者小于等于的无所谓，不必纠结这些细节）。

精度很低，1e-5都能过=。=

G++交

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include
      
        #define lson num<<1,s,mid #define rson num<<1|1,mid+1,e #define maxn 105 using namespace std; #define eps 1e-6 #define maxn 105 #define maxm 10005 struct node { int v,w,next; }edge[maxm]; int head[maxn]; bool in[maxn]; int d[maxn]; int ed[maxn]; int a,b,c,n,m,e,id; int bro,pli; void add(int a,int b,int c) { edge[id].v=b; edge[id].w=c; edge[id].next=head[a]; head[a]=id++; } void init() { memset(head,-1,sizeof(int)*(n+1)); memset(ed,0,sizeof(ed)); id=0; } void SPFA(int st) { queue
       
         Q; memset(in,0,sizeof(int)*(n+1)); memset(d,0x3f,sizeof(int)*(n+1)); Q.push(st); in[st]=1; d[st]=0; int tmp; while(!Q.empty()) { tmp=Q.front();Q.pop(); in[tmp]=0; for(int i=head[tmp];i!=-1;i=edge[i].next) { if(edge[i].v==pli) continue; if(d[edge[i].v]>d[tmp]+edge[i].w) { d[edge[i].v]=d[tmp]+edge[i].w; if(!in[edge[i].v]) { in[edge[i].v]=1; Q.push(edge[i].v); } } } } } int vis[maxn]; int db[maxn]; double mid; bool isok(int now) { vis[now]=1; if(d[now]*mid
        
         =eps) { memset(vis,0,sizeof(vis)); mid=(l+r)/2; if(isok(bro)) {tzf=1;r=mid;} else l=mid; } if(!tzf) puts("IMPOSSIBLE"); else printf("%.10lf\n",mid); } return 0; }