網頁

2014年4月5日 星期六

POJ 1724 ROADS

題目:
    總共N個點,給定R條道路,每條共有S,D,L,T代表S點到D點這條路長度L且須花費T元,題目求從1為起點,N為終點,在花費<=K元的情況下走到終點的最短距離。
    注意同一個S到D可能有多條道路。
想法:
    用Dis[i][j]表示"從起點1走到i點花費j元的最短距離",所以做SPFA的時候,每次就去更新Dis[i][0~K]的值,使其值盡可能的小,最後再去檢查Dis[N][0~K]的最小值是多少。
    因為S到D可能有多條道路,所以用vector來存較為簡單。