gj d062: 5.最短路徑 [brute force] [back tracking] [pruning]
- problem link
-
題目:感覺跟 TSP 有八成像www
-
解法: 可以發現大部分的點只有 3 個邊,且只有 16 個點
暴力枚舉的話約要 \(3^{16} = 43046721\) 個操作
還行!
所以就決定很懶惰的暴搜惹首先,最困難的部份
先用力的把圖給打進 code 裡吧 www要注意的是有時走回頭路反而更短
比如這樣的測資1 p o l
若是不回頭的話反而達不到最優解 3
故暴搜時不需排除已走過的節點第一次 AC 時幾乎沒剪枝,跑了 321ms
第二次用力的剪了一下,居然降到 3ms 惹wwww - \(T(n) = O(3^n)\)