網頁

2014年6月3日 星期二

UVa 10806 Dijkstra, Dijkstra

題意:
    給你一個無向圖,每條邊有cost,現在問如果不走已經走過的邊,則從S到T,然後再從T到S的最少cost是多少,如果無法達成則輸出"Back to jail"。

想法:
    最小cost最大流,S到T再從T到S,也就是T當作源點,S當作匯點,從T流到S,看是否能流過去2條,如果能則輸出min_cost,否則輸出"Back to jail"。
    因為同一條邊不能重複走,因此可以用一個二維矩陣used[][],在SPFA找"正向邊"的時候檢查used[i][j]!=true,除了code 82行和96行之外,其他都和MCMF模板一樣。