i, j 题
I. J
i :
j :
此题与i题的区别是两点间的距离变成了小点的两倍,dist(i,j)就不再一定是ij间的距离。如果ij间再经过一个x点,那么x点是值最小的点时距离是最小的,而中间再经过两个点一定会比经过一个点的距离大,所以到一个点,不经过多余点时的两点距离与经过最小点时的长度中小的那一个,便是所有值大于该点的点到该点的最短路
I. J
i :
j :
此题与i题的区别是两点间的距离变成了小点的两倍,dist(i,j)就不再一定是ij间的距离。如果ij间再经过一个x点,那么x点是值最小的点时距离是最小的,而中间再经过两个点一定会比经过一个点的距离大,所以到一个点,不经过多余点时的两点距离与经过最小点时的长度中小的那一个,便是所有值大于该点的点到该点的最短路
相关推荐