轉(zhuǎn)載請注明出處:http://www.klion.0fees.net/?p=39

首先得反省下我的比賽態(tài)度,對于這兩場比賽,我可以說沒有用心做.主要有下面幾點:
一.看題不細心,或者說根本就沒看過題,總是想讓隊友看題,然后自己想思路,這一點很不好,這一題就可以

看出來,如果當時我仔細看題的話,或許就能出了,就算我不能出,或許和隊友的討論中就能出來,后來導致

隊友一直一個人在搞這個題,我一直在醬油 – -||,這里向兩位隊友表示對不起.還有就是還沒看題就會有

點恐懼感,總怕自己不能做出來,這就是心態(tài)的問題了.我想下一場開始我會調(diào)好自己的心態(tài)的。
二.不能靜下心來仔細想題,這一點非常不好,感覺這兩場比賽自己做的很浮躁,很不好.可以說沒有共獻.
這幾天好好反思下自己,在下一場比賽爭取做的很好吧。加油！！！
下面說說這題的思路
對于那個ERROR At point x很好回答,只需要一個bool數(shù)組就可以解決了.剩下的就是第二問了,其實這可

以看成是Floyd的變體,對于Floyd算法,一共是3重循環(huán),最外面那一層是中間節(jié)點,在這里只不過把那一層

拆開了而已,也就是對于每一個marked的點,把這個點作為中間節(jié)點,然后更新所有點對的最短路(這里不用

管這兩個點是否被marked,因為如果沒有被marked的話,后面判斷的時候根本就不會用到這兩點的距離)這

樣的話,就相當于把Floyd的最外層拆成了一個一個的點,這樣時間復(fù)雜度是不變的,也就是O(V^3)的.對于

V<=300,完全OK.不過好像對于每個被marked的點進行所有點對的更新時可以在外層循環(huán)那加個判斷,但是

我沒想明白是什么。