[UVa] 10806 Dijkstra, Dijkstra.cpp

#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

#define INF 99999999
#define MAXN 205
vector<int> edge[MAXN];
int cap[MAXN][MAXN], flow[MAXN][MAXN], cost[MAXN][MAXN];
int pre[MAXN], dis[MAXN];
bool used[MAXN][MAXN];  // used[i][j] == true means edge(i,j) is used

void Initial(int N);
void MCMF(int S, int T);
bool SPFA(int S, int T);
void UpdateFlow(int S, int T, int bottleneck);

int main()
{
    int N, M;
    while (scanf("%d", &N) && N) {
        scanf("%d", &M);

        Initial(N);

        int u, v, t;
        for (int i = 0; i < M; ++i) {
            scanf("%d %d %d", &u, &v, &t);
            cap[u][v] = cap[v][u] = 1;
            cost[u][v] = cost[v][u] = t;
            edge[u].push_back(v);
            edge[v].push_back(u);
        }
        MCMF(N, 1);
    }
}
void Initial(int N)
{
    for (int i = 1; i <= N; ++i) edge[i].clear();
    memset(cap, 0, sizeof(cap));
    memset(flow, 0, sizeof(flow));
    memset(cost, 0, sizeof(cost));
    memset(used, 0, sizeof(used));
}
void MCMF(int S, int T)
{
    int min_cost = 0;
    int max_flow = 0;

    while (SPFA(S, T)) {
        UpdateFlow(S, T, 1);
        min_cost += dis[T];
        ++max_flow;
        if (max_flow >= 2) break;
    }
    if (max_flow < 2) puts("Back to jail");
    else printf("%d\n", min_cost);
}
bool SPFA(int S, int T)
{
    fill(begin(dis), end(dis), INF);
    queue<int> Q;
    bool inQueue[MAXN] = {0};

    dis[S] = 0;
    Q.push(S);
    inQueue[S] = true;

    while (!Q.empty()) {
        int cur = Q.front();
        Q.pop();
        inQueue[cur] = false;

        for (int nxt : edge[cur]) {
            if (flow[nxt][cur] > 0  && dis[cur] + (-cost[nxt][cur]) < dis[nxt]) {
                dis[nxt] = dis[cur] + (-cost[nxt][cur]);
                pre[nxt] = cur;
                if (!inQueue[nxt]) {inQueue[nxt] = true; Q.push(nxt);}
            }
            else if (!used[cur][nxt] && cap[cur][nxt] > flow[cur][nxt] && dis[cur] + cost[cur][nxt] < dis[nxt]) {
                dis[nxt] = dis[cur] + cost[cur][nxt];
                pre[nxt] = cur;
                if (!inQueue[nxt]) {inQueue[nxt] = true; Q.push(nxt);}
            }
        }
    }
    return dis[T] != INF;
}
void UpdateFlow(int S, int T, int bottleneck)
{
    for (int u = T; u != S; u = pre[u]) {
        flow[pre[u]][u] += bottleneck;
        flow[u][pre[u]] -= bottleneck;
        used[pre[u]][u] = used[u][pre[u]] = true;
    }
}