[Acwing] 1125.牛的旅行 floyd

前言

传送门 ：

思路

对于这题的答案 a n s = m a x { 加 边 前 的 最 大 值 , 加 边 后 的 最 大 值 } ans = max\{加边前的最大值,加边后的最大值\} ans=max{加边前的最大值,加边后的最大值}

因为数据范围很小所以我们可以跑 f l o y d floyd floyd

先求出所有点在加边前的最大值

最后在通过 m a x n [ i ] + m a x n [ j ] + d i s t ( i , j ) maxn[i]+maxn[j]+dist(i,j) maxn[i]+maxn[j]+dist(i,j)求出加边后的最大值

CODE

int n,m,t;
pdd q[N];
double d[N][N];
double maxn[N];
char g[N][N];

double get_dist(pdd a,pdd b)
{
	
	double dx = a.x - b.x;
	double dy = a.y - b.y;
	return sqrt(dx*dx + dy*dy);
}


void solve()
{
	cin>>n;
	for(int i=0;i>q[i].x>>q[i].y;
	for(int i=0;i>g[i];
	
	for(int i=0;i