转载请注明出处:http://www.klion.0fees.net/?p=39

首先得反省下我的比赛态度,对于这两场比赛,我可以说没有用心做.主要有下面几点:
一.看题不细心,或者说根本就没看过题,总是想让队友看题,然后自己想思路,这一点很不好,这一题就可以

看出来,如果当时我仔细看题的话,或许就能出了,就算我不能出,或许和队友的讨论中就能出来,后来导致

队友一直一个人在搞这个题,我一直在酱油 – -||,这里向两位队友表示对不起.还有就是还没看题就会有

点恐惧感,总怕自己不能做出来,这就是心态的问题了.我想下一场开始我会调好自己的心态的。
二.不能静下心来仔细想题,这一点非常不好,感觉这两场比赛自己做的很浮躁,很不好.可以说没有共献.
这几天好好反思下自己,在下一场比赛争取做的很好吧。加油！！！
下面说说这题的思路
对于那个ERROR At point x很好回答,只需要一个bool数组就可以解决了.剩下的就是第二问了,其实这可

以看成是Floyd的变体,对于Floyd算法,一共是3重循环,最外面那一层是中间节点,在这里只不过把那一层

拆开了而已,也就是对于每一个marked的点,把这个点作为中间节点,然后更新所有点对的最短路(这里不用

管这两个点是否被marked,因为如果没有被marked的话,后面判断的时候根本就不会用到这两点的距离)这

样的话,就相当于把Floyd的最外层拆成了一个一个的点,这样时间复杂度是不变的,也就是O(V^3)的.对于

V<=300,完全OK.不过好像对于每个被marked的点进行所有点对的更新时可以在外层循环那加个判断,但是

我没想明白是什么。