HDU/HDOJ 3832 Earth Hour

この問題は私が先に問題の意味をはっきり見なかった.2から3だと思った
結果は1,2,3でつながっているので、問題は明らかです.以前ジャンプボードの問題をしたことがあります.
これとよく似ています.
方法は,それぞれ1,2,3を単一ソース最短にし,ジャンプボードiを列挙することである.
dis 1[i]+dis 2[i]+dis 3[i]を最小にします.
そして処理すると本題の答えです
マイコード:
 

#include<stdio.h>
#include<vector>
#include<queue>
#include<algorithm>
#define inf 99999999

using namespace std;

struct cir
{
	int x;
	int y;
	int r;
};
struct node
{
	int v;
	int len;
};
vector<node>map[205];
int n;

void spfa(int s,int dis[])
{
	int i,pre[205];
	bool used[205];
	queue<int>q;
	memset(used,0,sizeof(used));
	memset(pre,-1,sizeof(pre));
	for(i=0;i<205;i++)
		dis[i]=inf;
	dis[s]=0;
	used[s]=true;
	q.push(s);
	while(!q.empty())
	{
		int u=q.front();
		q.pop();
		used[u]=false;
		for(i=0;i<map[u].size();i++)
		{
			node p=map[u][i];
			if(dis[p.v]>dis[u]+p.len)
			{
				dis[p.v]=dis[u]+p.len;
				pre[p.v]=u;
				if(!used[p.v])
				{
					used[p.v]=true;
					q.push(p.v);
				}
			}
		}
	}
}

void init()
{
	int i;
	for(i=0;i<=n;i++)
		map[i].clear();
}

int max(int a,int b)
{
	if(a>b)
		return a;
	else
		return b;
}

int main()
{
	int t,i,dist1,dist2,j,ans;
	cir c[205];
	node p;
	int dis1[205],dis2[205],dis3[205];
	scanf("%d",&t);
	while(t--)
	{
		init();
		scanf("%d",&n);
		for(i=1;i<=n;i++)
			scanf("%d%d%d",&c[i].x,&c[i].y,&c[i].r);
		for(i=1;i<=n;i++)
		{
			for(j=i+1;j<=n;j++)
			{
				dist1=(c[i].x-c[j].x)*(c[i].x-c[j].x)+(c[i].y-c[j].y)*(c[i].y-c[j].y);
				dist2=(c[i].r+c[j].r)*(c[i].r+c[j].r);
				if(dist1<=dist2)
				{
					p.v=j;
					p.len=1;
					map[i].push_back(p);
					p.v=i;
					map[j].push_back(p);
				}
			}
		}
		spfa(1,dis1);
		spfa(2,dis2);
		spfa(3,dis3);
		ans=-1;
		for(i=1;i<=n;i++)
		{
			if(dis1[i]<inf&&dis2[i]<inf&&dis3[i]<inf)
				ans=max(ans,n-(dis1[i]+dis2[i]+dis3[i]+1));
		}
		printf("%d
",ans);
	}
	return 0;
}