和SGU 185 Two shortest有點(diǎn)類似。。就是求從源點(diǎn)到終點(diǎn)的再從終點(diǎn)到源點(diǎn)的最短路，但是不能經(jīng)過同一條邊兩次。
費(fèi)用流，原來邊的長度作為花費(fèi)，容量為1，再建新源點(diǎn)到舊源點(diǎn)容量為2，新匯點(diǎn)和舊匯點(diǎn)容量為2，求最小費(fèi)用就為最短路徑。如果不存在則新源點(diǎn)到舊源點(diǎn)的容量小于2。
這題貌似也有多種解法。費(fèi)用流不唯一。
#include <iostream>
using namespace std;
#define N 105
#define INF 1 << 29
struct node
{
int cap, cost;
}g[N][N];
int pre[N], d[N], map[N][N];
bool spfa(int src, int sink)
{
int que[N * N], front, top, u;
bool in[N];
for(int i = 0; i <= sink; i++)
{
d[i] = INF;
in[i] = 0;
}
in[src] = 1;
d[src] = front = top = 0;
pre[src] = src;
que[top++] = src;
while(front < top)
{
u = que[front++];
in[u] = 0;
for(int i = 0; i <= sink; i++)
{
if(g[u][i].cap > 0 && d[u] + g[u][i].cost < d[i])
{
d[i] = d[u] + g[u][i].cost;
pre[i] = u;
if(!in[i])
{
que[top++] = i;
in[i] = 1;
}
}
}
}
return d[sink] != INF;
}
int mincost(int src, int sink)
{
int ans = 0, flow;
while(spfa(src, sink))
{
flow = INF;
for(int i = sink; i != src; i = pre[i])
{
if(flow > g[pre[i]][i].cap)
flow = g[pre[i]][i].cap;
}
for(int i = sink; i != src; i = pre[i])
{
g[pre[i]][i].cap -= flow;
g[i][pre[i]].cap += flow;
g[i][pre[i]].cost = -g[pre[i]][i].cost;
}
ans += d[sink] * flow;
}
return ans;
}
int main()
{
int n, m, ans;
while(scanf("%d", &n), n)
{
scanf("%d", &m);
memset(g, 0, sizeof(g));
for(int i = 0; i < m; i++)
{
int a, b, c;
scanf("%d %d %d", &a, &b, &c);
g[a][b].cap = g[b][a].cap = 1;
g[a][b].cost = g[b][a].cost = c;
}
g[0][1].cap = g[1][0].cap = 2;
g[n][n + 1].cap = g[n + 1][n].cap = 2;
ans = mincost(0, n + 1);
if(g[0][1].cap) puts("Back to jail");
else printf("%d\n", ans);
}
return 0;
}