Dijkstra, Dijkstra.cpp

#include <iostream>
#include <vector>

using namespace std;

#define INFINITO 1000000
#define forn(i, n) for(i = 0; i < (n); ++i)

typedef vector<int> vint;
typedef vector<vint> vvint;

vvint capacidad; // C[u, v] - F[u, v]
vvint costos;

int bellman_ford(vint& predecesores) {
	int n = costos.size(), i, j, k;
	vint dist(n, INFINITO);
	predecesores.resize(n);
	dist[0] = 0;
	forn(i, n) forn(j, n) forn(k, n) {
		if(capacidad[j][k] != 0 && dist[k] > costos[j][k] + dist[j]) {
			dist[k] = costos[j][k] + dist[j];
			predecesores[k] = j;
		}
	}	
	return dist[n-1];
}

void fluir(vint& predecesores) {
	int u, v = predecesores.size()-1;
	while(v) {
		u = predecesores[v];
		capacidad[u][v]--;
		capacidad[v][u]++;
		if(capacidad[v][u] == 2) costos[v][u] *= -1; //  F[v, u] = -1
		v = u;
	}
}

int main() {
	int n, m, u, v, c;
	cin >> n;
	while(n) {
		cin >> m;
		costos.clear();
		capacidad.clear();		
		costos.resize(n, vint(n, INFINITO));
		capacidad.resize(n, vint(n, 0));
		
		while(m--) {
			cin >> u >> v >> c;
			u--; v--;
			costos[u][v] = costos[v][u] = c;			
			capacidad[u][v] = capacidad[v][u] = 1;
		}
		
		vint predecesores;
		int min = bellman_ford(predecesores);
		fluir(predecesores);
		min += bellman_ford(predecesores);
		if(min >= INFINITO) cout << "Back to jail" << endl;
		else cout << min << endl;
						
		cin >> n;
	}
}