做法離不開窮舉 2 個 terminal, 再計算 route distance
一開始以為剩返的 N-2 個 bus stop 會選擇連去離他最近的那個 terminal, 不過後來發現反例
解決方法有點像greedy (看contest report)
窮舉 terminal i,j
先把剩下的 N-2 個 bus stop 都連去 i
然後按 dist[k][i]的 decreasing order, 嘗試把 k 調到 j 看看能不能使最大距離下降
有點詭異的過了..
很直觀做法但又無prove過..
No comments:
Post a Comment