發表新討論
#29726: Dijkstra + DP


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

學校 : 國立交通大學
編號 : 95834
來源 : [140.113.213.76]
最後登入時間 ：
2023-09-25 22:02:42
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
來源 : [36.229.39.123]
最後登入時間 ：
2024-04-19 20:42:42
g733. 110北二4.漫遊高譚市 -- 110北二區桃竹苗資訊學科能力複賽 | From: [114.43.78.160] | 發表日期 : 2022-03-26 00:30

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

 
ZeroJudge Forum