Watch Dog 最小生成树_综合

Watch Dog [最小生成树] 时间限制: 1 Sec 内存限制: 128 MB

提交: 109 解决: 31 统计

题目描述

在2050年某城市，一个神秘组织通过一种名叫ctOS的控制系统掌控了全城所有人的联网设备（手机、电脑、监控、交通信号灯，甚至是银行警察局的安保系统），该系统通过很多遍布城市各地的基站来完成对电子设备的控制。

Aiden Pearce（艾登·皮尔斯）是一名超级黑客，因他叛出该组织而被组织报复，谋划了一场"车祸"害死了他的女儿。艾登为了给女儿报仇，决心铲除该组织。

首先他要先侵入stOS系统获取该组织的资料，然而这些资料被分散存到了所有的基站中，所以他要用自己改装的手机获取所有基站的访问权。他的手机电量有限，如果电量为0以下，则无法继续进行工作。幸运的是，艾登可以通过已经侵入的基站，将其作为傀儡机，继续入侵其它的基站。所消耗的电量为两个设备（手机~基站、基站~基站）距离的平方。

举个例子，艾登的初始位置为(0,0)，有两个基站的位置分别为(1,0)(0,2)，艾登可以先从他的位置入侵第一个基站，耗电为1；再通过第一个基站，入侵第二个基站，耗电为5。总耗电为6。

输入

有多组测试数据。

每组数据第一行输入两个整数n和k，n表示一共有n个基站，k表示现在手机的电量。

接下来一行输入两个整数p,q。表示艾登现在的位置。

接下来的n行，每行输入两个两个整数：X_i,Y_i。表示第i个基站的位置。

1≤n≤500

0≤k≤109

?200≤x,y,Xi,Yi≤200

输出

对于每组数据，输出占一行。

如果艾登可以入侵所有的基站，输出："Go ahead!"（不带引号）

如果艾登不能入侵所有的基站，输出："Go a head!"（不带引号）

样例输入

样例输出

Go ahead!
Go a head!

#include<bits/stdc++.h>
const long long inf=1e10+5;
using namespace std;
struct node{int x,y;
}a[1005];
int main()
{int n,k;while(~scanf("%d%d",&n,&k)){for(int i=0;i<=n;i++){scanf("%d%d",&a[i].x,&a[i].y);}long long d[1005];for(int i=0;i<=n;i++)d[i]=inf; int s=0;long long sum=0;int v[1005]={0};for(int i=1;i<=n;i++){long long maxx=inf,g;for(int j=1;j<=n;j++){if(v[j]==0){if(d[j]>(a[j].x-a[s].x)*(a[j].x-a[s].x)+(a[j].y-a[s].y)*(a[j].y-a[s].y))d[j]=(a[j].x-a[s].x)*(a[j].x-a[s].x)+(a[j].y-a[s].y)*(a[j].y-a[s].y);if(d[j]<=maxx){maxx=d[j];g=j;}}	}sum+=maxx;s=g;v[s]=1;}if(sum<=k)cout<<"Go ahead!\n";else cout<<"Go a head!\n";}
}