UVA10806 用SPFA

Jim Abrahams and Pat Proft,
"Hot Shots! Part Deux."

You are a political prisoner in jail. Things are looking grim, but fortunately, your jailmate has come up with an escape plan. He has found a way for both of you to get out of the cell and run through the city to the train station, where you will leave the country. Your friend will escape first and run along the streets of the city to the train station. He will then call you from there on your cellphone (which somebody smuggled in to you inside a cake), and you will start to run to the same train station. When you meet your friend there, you will both board a train and be on your way to freedom.

Your friend will be running along the streets during the day, wearing his jail clothes, so people will notice. This is why you can not follow any of the same streets that your friend follows - the authorities may be waiting for you there. You have to pick a completely different path (although you may run across the same intersections as your friend).

What is the earliest time at which you and your friend can board a train?

Problem, in short
Given a weighed, undirected graph, find the shortest path from S to T and back without using the same edge twice.

Input
The input will contain several test cases. Each test case will begin with an integer n (2<=n<=100) - the number of nodes (intersections). The jail is at node number 1, and the train station is at node number n. The next line will contain an integer m - the number of streets. The next m lines will describe the m streets. Each line will contain 3 integers - the two nodes connected by the street and the time it takes to run the length of the street (in seconds). No street will be longer than 1000 or shorter than 1. Each street will connect two different nodes. No pair of nodes will be directly connected by more than one street. The last test case will be followed by a line containing zero.

Output
For each test case, output a single integer on a line by itself - the number of seconds you and your friend need between the time he leaves the jail cell and the time both of you board the train. (Assume that you do not need to wait for the train - they leave every second.) If there is no solution, print "Back to jail".

2 1 1 2 999 3 3 1 3 10 2 1 20 3 2 50 9 12 1 2 10 1 3 10 1 4 10 2 5 10 3 5 10 4 5 10 5 7 10 6 7 10 7 8 10 6 9 10 7 9 10 8 9 10 0

Back to jail 80 Back to jail

Problemsetter: Igor Naverniouk

题意：有A，B两个人要越狱，A成功地从监狱到达火车站时B立即出发，两个人的路线不能有重合（可以重合点，不可以重合边），需要两个人路径和最短，求最短路径和。
抽象一点，就是找到从点S到T的最短长度的环（即：两次路径不能有重边）

思路：最大流的方法可以做，我用的是两次SPFA，相当于求两次最短路:先求一次最短路，然后把最短路上的S->T方向的边长赋值为INF，反向边长赋值为-map[u][v],即原来长度的相反数，然后再次SPFA,两次结果相加即可。
对于标记为反向长度取反，如果不懂，请看下图：

输入数据为：
4
5
1 2 1
2 3 1
3 4 1
1 3 10
2 4 10

上图中红色路线为第一条最短路，绿色路线为第二条最短路。两条最短路有公共边，这时候每条路线可以看成：前一部分+公共边+后一部分，在公共边处由于做了反向长度的标记，那么公共部分相当于没有走（长度相互抵消了），实际效果等价于“红色路线的前一部分+绿色路线的后一部分”作为第一条路线，“绿色路线前一部分+红色路线后一部分”作为第二条路线。

#include <stdio.h>
#include <iostream>
#include <queue>
#include <string.h>
using namespace std;
const int INF = 0x3f3f3f3f;
const int MAXN = 100 + 5;
int map[MAXN][MAXN];
int vis[MAXN];
int d[MAXN];
int fa[MAXN];
void init(int n){
    int i, j;
    for(i=1; i<=n; i++){
        for(j=1; j<=n; j++){
            if(i!=j) map[i][j] = INF;
            else map[i][j] = 0;
        }
    }
}
int SPFA(int S, int T, int n){
    int i;
    memset(vis, 0, sizeof(vis));
    memset(d, 63, sizeof(d));
    d[S] = 0;
    queueq;
    q.push(S);
    vis[S] = 1;
    while(!q.empty()){
        int x = q.front();
        q.pop();
        vis[x] = 0;
        for(i=1; i<=n; i++){
            if(d[i]>d[x]+map[x][i]){
                d[i] = d[x] + map[x][i];
                fa[i] = x;
                if(!vis[i]){
                    vis[i] = 1;
                    q.push(i);
                }
            }
        }
    }
    return d[T];
}
int main(){
//    freopen("in.txt", "r", stdin);
    int n, m;
    while(scanf("%d", &n)!=EOF && n){
        scanf("%d", &m);
        init(n);
        int i, u, v, w;
        for(i=1; i<=m; i++){
            scanf("%d%d%d", &u, &v, &w);
            if(map[u][v]>w){
                map[u][v] = map[v][u] = w;
            }
        }
        int S = 1, T = n;
        int ans1 = SPFA(S, T, n);
        while(T!=S){
            map[T][fa[T]] = -map[T][fa[T]];
            map[fa[T]][T] = INF;
            T = fa[T];
        }
        T = n;
        int ans2 = SPFA(S, T, n);
        if(ans1 >= INF || ans2 >= INF) printf("Back to jail\n");
        else printf("%d\n", ans1 + ans2);
    }
}