IOI 2002 The Troublesome Frog

用了一個看似是 O(N³) 的方法做..

pick 2 點, check 下佢可唔可以成為 path 的頭 2 點, 然後再行條 path , 睇下係咪 path 上的每一點都存在

另外很重要是加了一些優化

1. 由左面的點開始做
2. 如果假設條 path 是 valid 但長度也不長於 current max, 就唔使 check 了

所以看似是 O(N³) 的方法在 pku 只 run 了 16ms


不過再想, 其實可能是 O(N²) 來的

照解題報告的方法, 如果將兩點 (A,B) 視為一個 vertex, 咁只有 N² 個 vertex

而由於加了那2個優化, 應該可以確保每個 vertex 最多只行一次