UVa 116 Unidirectional TSP

簡化版旅行推銷員問題,用DP解

這題我的醒悟就是,用演算法不要太死腦筋
因為這題有一個機歪點,就是如果有多條權重相同的最短路徑,要輸出字典順序最小的那一條。

如果從起點往後DP,那麼字典順序很難解
如果從終點DP回來起點,那麼字典順序自然而然解決了。

瞭解演算法以後,果然還是要靈活使用才行。


附上測資
應該足夠應付各種狀況了

留言

這個網誌中的熱門文章

讀書心得: 撒哈拉的故事

OpenGL FAQ: 8. 使用視圖與相機鏡頭轉換,及 gluLookAt()

讀書心得: 你以為你以為的就是你以為的嗎?