2009年4月28日 星期二

UVa 116 Unidirectional TSP

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

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

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

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


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