、因为两个点相交,这个点的值只能加一次,然而我们肯定能找到一条绕过这个点走到下个点的路径,这条路径一定是大于等于之前相交路径的
数学表达就是:两条路径在一个点,那么在这个点加的值就是0+g[i,j] 但是我们可以让其中一条路径绕过这个点再走到这个点的下一个点 那么加的值应该是g[i,j-1] + g[i,j] 因为是非负数,所以我们可以找到一条大于等于之前有相交点的路径,那么这个有相交点的一定不是最优解;即便这条路径是最优解也有另一条最优解和这个路径和一样,但是我们只需要输出路径和就可以了,最优解路径有可能是有相交点的,但是也有另一个最优解没有相交点,那么我们输出的路径和肯定可以是一条没有相交点的最优解