有兩種想法

一種是用MOVIE為關係去畫一個牛之間的相鄰圖

這樣worst case是O(N^2 M) (建表

 

另外是以一個MOVIE為基準 去搜查該MOVIE跟哪些MOVIE相連

做BFS

然後查TABLE找最短DISTANCE

這樣worst case是O(N^2 * M * NM) (枚舉任兩點 然後用BFS求最短距離

 

怎麼看都是第二種比較差

雖然第一種看起來不甚佳 但測資好像沒有那種很糟糕的

所以蠻快就過了

 

http://nopaste.csie.org/a9c5f

arrow
arrow
    全站熱搜

    robertanders 發表在 痞客邦 留言(0) 人氣()

    E-mail轉寄