網頁

2014年4月16日 星期三

UVa 11833 Route Change

題意:
    第一行有N M C K四個數字,N表示有N個地點(編號0~N-1),M表示有M條路線,C-1為終點編號,K為出發點編號。
    底下有M行,每行u v d三個數字,分別表示u到v和v到u這條路線需要花費d元。
    本題特別的要求為,0~C-1為特殊地點,只要踏入0~C-1這C個地點內,例如i這個點<=C-1,之後的路徑就只能依照i, i+1, i+2, .....,C-1這樣走,只要不在特殊地點,就能前往任意其他地方,本題求K到C-1的最小花費。

想法:
    依題目輸入將M條路線建好dis[u][v]=d,其他沒有連通的路線為INF。輸入完成後我們將編號小於C-1的點i,算出dis[i][C-1],等等SPFA用到。
    然後做K到C-1的SPFA最短路徑,注意如果踏入的點(nxt)為特殊地點(nxt<C),不要丟入queue裡面,而是直接判斷cost[C-1]=min(cost[C-1], cost[nxt]+dis[nxt][C-1]),其他不是特殊地點的nxt,則依照一般SPFA把nxt丟入queue即可。