pick 2 點, check 下佢可唔可以成為 path 的頭 2 點, 然後再行條 path , 睇下係咪 path 上的每一點都存在
另外很重要是加了一些優化
- 由左面的點開始做
- 如果假設條 path 是 valid 但長度也不長於 current max, 就唔使 check 了
所以看似是 O(N3) 的方法在 pku 只 run 了 16ms
不過再想, 其實可能是 O(N2) 來的
照解題報告的方法, 如果將兩點 (A,B) 視為一個 vertex, 咁只有 N2 個 vertex
而由於加了那2個優化, 應該可以確保每個 vertex 最多只行一次
No comments:
Post a Comment