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;
}