学步园

大意：从起点走到终点，然后从终点走到起点，其中不能同时走过相同的一条边，问你最小路径长度。

思路：把无向边拆边，起点到终点求一次最短路径，将最短路径经过的边记录下来，然后把最短路径上的边不同的删除，相同的取相反数（第二次最短路径以终点为原来的起点），然后再做一次最短路径，这样，就可以保证两次的总长度是最短的。

不能求一次最短路径，然后把经过的最短路径删除，这样的做法求得的不一定是最优的，具体应该是上面的做法，这样就类似于经过了公用边，但是公用的权值却没有加入总的权值里面，而第一次和第二次经过的路径却是最短的，相当于两次最短路径交换了路径走到终点。

#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <cstdio>
#include <queue>
#include <cmath>
using namespace std;

const int MAXN = 1010;
const int INF = 0x3f3f3f3f;

int G[MAXN][MAXN];
int d[MAXN];
int fa[MAXN];

int n, m;
int src, end;

void init()
{
	memset(G, INF, sizeof(G));
	memset(fa, -1, sizeof(fa));
}

int spfa(int src, int end)
{
	queue<int> q;
	bool inq[MAXN] = {0};
	for(int i = 1; i <= n; i++) d[i] = (i == src)? 0:INF;
	q.push(src);
	while(!q.empty())
	{
		int u = q.front(); q.pop();
		inq[u] = 0;
		for(int v = 1; v <= n; v++) if(G[u][v])
		{
			if(d[v] > d[u] + G[u][v])
			{
				d[v] = d[u] + G[u][v];
				fa[v] = u;
				if(!inq[v])
				{
					inq[v] = 1;
					q.push(v);
				}
			}
		}
	}
	return d[end];
}

int read_case()
{
	init();
	scanf("%d", &n);
	if(!n) return 0;
	scanf("%d", &m);
	while(m--)
	{
		int u, v, w;
		scanf("%d%d%d", &u, &v, &w);
		G[u][v] = G[v][u] = w;
	}
	return 1;
}

void change(int u) /*删除相反边，最短路径上的边赋值为相反数*/
{
	
	if(fa[u] == -1) return ;
	G[fa[u]][u] = -G[fa[u]][u];
	G[u][fa[u]] = INF;
	change(fa[u]);
}

void solve()
{
	int ans = spfa(1, n);
	change(n);
	ans += spfa(n, 1);
	if(ans < INF) printf("%d\n", ans);
	else printf("Back to jail\n");
}

int main()
{
	while(read_case())
	{
		solve();
	}
	return 0;
}