發表新討論
#29726: Dijkstra + DP


SUNGOD (黑龍炎使．煞氣ㄟSUNGOD)

學校 : 國立交通大學
編號 : 95834
來源 : [1.169.219.170]
最後登入時間 ：
2024-05-31 14:37:13
g733. 110北二4.漫遊高譚市 -- 110北二區桃竹苗資訊學科能力複賽 | From: [36.225.73.138] | 發表日期 : 2022-03-25 21:03

令DP[n][4]表示到點s到各點i且[只用鐵路m1/只用鐵路m2/交換過一次到m1/交換過一次到m2]的最短距離

然後稍微修改一下Dijkstra的轉移判斷，例如DP[i][0]要用m2鐵路到j就得跟DP[j][3]比，以此類推即可。

 
#29727: Re:Dijkstra + DP


rollfc (胖胖貓)

學校 : 國立清華大學
編號 : 81012
來源 : [49.216.18.187]
最後登入時間 ：
2024-11-10 10:25:04
g733. 110北二4.漫遊高譚市 -- 110北二區桃竹苗資訊學科能力複賽 | From: [114.43.78.160] | 發表日期 : 2022-03-26 00:30

和 UVA-10269. Adventure of Super Mario 滿類似的

 
ZeroJudge Forum