# 題目: UVa 10806 - Dijkstra, Dijkstra
# 題目說明
給一個無向圖，有 N 個點及 M 條邊，每條邊的 capacity 為 1 、有不同的 cost
求從起點 S 走到終點 T 兩次，求總和最小的 cost
INPUT:
每筆測資先輸入兩個整數 N 、 M
接下來有 M 行，每行輸入三個整數 u 、 v 、 c ，代表 edge(u, v) 的 cost 為 c ;
OUTPUT:
輸出最小的 cost ，若無法從起點走到終點兩次則輸出 Back to jail
# 解題方法
此題的解題概念為 Minimum cost Maximum flowMaximum flow 的部分使用 Ford Fulkerson 演算法Minimum cost 則使用佇列最佳化的 bellman ford 演算法，又稱 Shortest Path Faster Algorithm ，簡稱 SPFA
基本上與 Maximum flow 的程式碼相同，只是搜尋起點 S 是否可以走到終點 T 時不再是隨便走，而是用 SPFA 找到 minimum cost 的路徑
由於每條路只能走一次，所以將 capacity 設為 1
使用一個變數 cnt 紀錄從起點 S 走到終點 T 的次數
# 參考程式碼
#include <iostream> | |
#include <vector> | |
#include <queue> | |
#include <climits> | |
#define vvint vector< vector<int> > | |
#define vint vector<int> | |
using namespace std; | |
static auto fast_io = [] | |
{ | |
ios::sync_with_stdio(false); | |
cout.tie(nullptr); | |
cin.tie(nullptr); | |
return 0; | |
}(); | |
int N, M; | |
int _s = 1, _t; | |
vvint edge; | |
vvint cost; | |
vvint capacity; | |
vvint net; | |
vint dis; | |
vint p; | |
void init() | |
{ | |
_t = N; | |
edge.assign(110, vint()); | |
cost.assign(110, vint(110, 0)); | |
capacity.assign(110, vint(110, 0)); | |
net.assign(110, vint(110, 0)); | |
p.assign(110, 0); | |
} | |
void read() | |
{ | |
int u, v, c; | |
cin >> M; | |
for (int i = 0; i < M; ++i) | |
{ | |
cin >> u >> v >> c; | |
edge[u].emplace_back(v); | |
edge[v].emplace_back(u); | |
cost[u][v] = cost[v][u] = c; | |
capacity[u][v] = capacity[v][u] = 1; | |
} | |
} | |
bool bellman() | |
{ | |
dis.assign(110, INT_MAX); | |
dis[_s] = 0; | |
queue<int> Q; | |
vint inQ(110, false); | |
Q.emplace(_s); | |
inQ[_s] = true; | |
while (!Q.empty()) | |
{ | |
int u = Q.front(); | |
Q.pop(); | |
inQ[u] = false; | |
for (auto& v : edge[u]) | |
{ | |
if (net[v][u] > 0 && dis[u] + (-cost[v][u]) < dis[v]) | |
dis[v] = dis[u] + (-cost[v][u]); | |
else if (capacity[u][v] > net[u][v] && dis[u] + cost[u][v] < dis[v]) | |
dis[v] = dis[u] + cost[u][v]; | |
else continue; | |
p[v] = u; | |
if (!inQ[v]) Q.emplace(v), inQ[v] = true; | |
} | |
} | |
if (dis[_t] == INT_MAX) return false; | |
else return true; | |
} | |
void updateflow(int u, int v, int c) | |
{ | |
if (v == _s) return; | |
net[u][v] += c; | |
net[v][u] -= c; | |
updateflow(p[u], u, c); | |
} | |
void maxflow() | |
{ | |
int ret = 0, cnt = 0; | |
while (bellman() && ++cnt <= 2) | |
{ | |
ret += dis[_t]; | |
updateflow(p[_t], _t, 1); | |
} | |
if (cnt < 2) cout << "Back to jail\n"; | |
else cout << ret << "\n"; | |
} | |
int main() | |
{ | |
while (cin >> N, N) | |
{ | |
init(); | |
read(); | |
maxflow(); | |
} | |
} |
