这道题与模板的区别只在没有直接告诉你权值
只需要用两点之间求距离公式即可 sqrt((x1−x2)2+(y1−y2)2)
其余的,我们可以用一个二维数组存(x, y)
求出权值后建图,然后模板一套!
但是注意,我们需要每一个点与其他所有点的权值
用c++的话说就是,套两个循环
for (int i = 1; i <= n; i++) {
for (int j = i + 1; j <= n; j++) {
double w = 公式
}
}
整理一下:
首先,输入
用数组存(x, y)
然后用循环和两点距离公式建图
跑最小生成树
然后看猴子的跳跃距离是不是大于最小生成树的值