这是一个单源最短路的变形，枚举的是关节点；
小技巧：在开始用三次dijstra算法求出三个关键点到所有其他点的距离，保存下来，枚举关节点时就不要每一次都求解，以节省时间，否则会超时。
思维：这里卡的是转换过程，另外一个是知识点，对于知识点现在已经学过了，以后要加油，对于思维的转化，还是要靠经验的积累和考场的思考。
#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
#define INF 10000000
int a[210][3];
int l[210][210];
int d1[210],d2[210],d3[210];
void initiate(int n)
{
for( int i=0; i<n; ++i )
for(int j=0; j<n; ++j )
{
int r = a[i][2]+a[j][2];
int len = ( a[i][0] - a[j][0] )*( a[i][0] - a[j][0] ) + ( a[i][1] - a[j][1] )*( a[i][1] - a[j][1] );
if( r*r >= len )
{
l[i][j] = 1;
l[j][i] = 1;
}
}
for(int i=0; i<n; ++i)
l[i][i]=0;
}
void dijstra(int i,int n,int d[])//每一次选取已有集合的最小d值,更新其他d值
{
d[i] = 0;
int flag[210];
memset(flag,0,sizeof(flag));
int tt=n;
while( tt-- )
{
int max =INF ;
int num ;
for(int j=0; j< n; j++ )
if( d[j] < max && (flag[j] == 0) )
{
max = d[j];
num = j;
}
flag[num] = 1;
for( int t=0; t<n; ++t )
{
if( flag[t] == 0 && l[num][t] == 1 )
{
if( d[t] > (d[num]+1) )
{
d[t] = d[num]+1;
}
}
}
}
}
int main()
{
int t;
scanf("%d",&t);
while( t-- )
{
int n;
scanf("%d",&n);
memset(l,0,sizeof(l));
//printf("n:%d\n",n);
for( int i=0; i<n; ++i )
scanf("%d%d%d",&a[i][0],&a[i][1],&a[i][2]);
int w=n;
initiate(w);
for( int k=0; k<210; ++k )
{
d1[k] = INF;
d2[k] = INF;
d3[k] = INF;
}
dijstra(0,n,d1);
dijstra(1,n,d2);
dijstra(2,n,d3);
int min =INF;
for( int j=0; j<n; ++j)
if( min > d1[j]+d2[j]+d3[j] )
min = d1[j]+d2[j]+d3[j];
if( min == INF )
printf("-1\n");
else
printf("%d\n",(n-min-1));
}
return 0;
}