Description
Input
Output
Sample Input
3 5 1 1 1 1 4 1 4 1 1 2 2 1 3 3 1 7 1 1 1 4 1 1 2 4 1 1 3 1 3 1 1 3 3 1 4 3 1 6 1 1 1 5 1 1 5 5 1 3 1 2 5 3 2 3 3 1
Sample Output
-1 2 1
题目转化一下也就是要用灯将1和2和3连接在一起，并且要最少的灯将他们连接在一起。
将3个连接在一起总会有一个节点，这个点分别连接其他的三个点的最短，用1 2 3 分别求出对其它所有点的最短路，在枚举所有点为节点，求出最小的值，就是需要最小的值把1 2 3 连接在一起，用n减去 得到结果
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#define INF 300
using namespace std;
struct node{
int x , y , r ;
} p[300];
int mm[300][300] , a[300] ;
int dis[300] , vis[300] ;
void dij(int n,int u)
{
int i , j , min1 , k ;
memset(vis,0,sizeof(vis));
for(i = 0 ; i <= n ; i++)
dis[i] = mm[u][i] ;
dis[u] = 0 ;
vis[u] = 1 ;
for(i = 1 ; i <= n ; i++)
{
min1 = INF ;
for(j = 1 ; j <= n ; j++)
if( !vis[j] && dis[j] < min1 )
{
min1 = dis[j] ;
k = j ;
}
if(min1 == INF)
break;
vis[k] = 1 ;
for(j = 1 ; j <= n ; j++)
if( !vis[j] && dis[j] > dis[k] + mm[k][j] )
dis[j] = dis[k] + mm[k][j] ;
}
}
int main()
{
int t , i , j , n , m ;
scanf("%d", &t);
while(t--)
{
scanf("%d", &n);
for(i = 1 ; i <= n ; i++)
{
scanf("%d %d %d", &p[i].x, &p[i].y, &p[i].r);
for(j = 1 ; j <= i ; j++)
{
double l = sqrt( (p[i].x-p[j].x)*(p[i].x-p[j].x)*1.0 + (p[i].y-p[j].y)*(p[i].y-p[j].y)*1.0 );
if(l <= ( p[i].r + p[j].r ))
mm[i][j] = mm[j][i] = 1 ;
else
mm[i][j] = mm[j][i] = INF ;
}
}
memset(a,0,sizeof(a));
dij(n,1);
for(i = 1 ; i <= n ; i++)
a[i] += dis[i] ;
dij(n,2);
for(i = 1 ; i <= n ; i++)
a[i] += dis[i] ;
dij(n,3);
for(i = 1 ; i <= n ; i++)
a[i] = n - (a[i] + dis[i] + 1) ;
int max1 = -1 ;
for(i = 1 ; i <= n ; i++)
if( a[i] > max1 )
max1 = a[i] ;
if(max1 < 0 )
printf("-1\n");
else
printf("%d\n", max1);
}
return 0;
}
复习--F - Earth Hour（最短路，连接1 2 3个点）,布布扣,bubuko.com
复习--F - Earth Hour（最短路，连接1 2 3个点）
原文：http://blog.csdn.net/winddreams/article/details/38341177