いっしょに面白くて最もショートします。

http://codeforces.com/contest/29/problem/E
二つの動点の最短問題は、二つの点が同時に移動し、同時に同じ点に到達できないことを要求します。二つの点はずっと移動して待つことができなく、同時にそれぞれの目標点に到達する最短ルートを求めます。
状態空間[a][b][c]（1<=a==n，1<=b==n，0<=c==1）は、動点0がaにあり、動点1がbにあり、現在は動点cに移動する番です。検索の初期状態は[1][n][0]で、終了状態は[n][1][0]で、bfsで結構です。

#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <map>
#include <stack>
#include <queue>
#include <climits>

using namespace std;

typedef long long LL;
typedef unsigned long long ULL;

const int MAXN(501);
const int MAXE(20010);
const int INFI((INT_MAX-1)/2);
const ULL LIM(1000000000000000000ull);
template<typename T>
bool checkmin(T &a, const T &b){
    return b < a? (a = b, true): false;
}

template<typename T>
bool checkmax(T &a, const T &b){
    return b > a? (a = b, true): false;
}

inline int lowb(int i){return i&-i;}
int gcd(int a, int b){
    while(b){
        int t = a%b;
        a = b;
        b = t;
    }
    return a;
}

bool vi[MAXN][MAXN][2];
int pre[MAXN][MAXN][2];
struct Q{
    int a, b, c, d;
    Q(){}
    Q(int a_, int b_, int c_, int d_): a(a_), b(b_), c(c_), d(d_){}
} q[MAXN*MAXN*2];
int fr, ba;
// Graph
struct E{
    int v;
    E *next;
};
struct G{
    E e[MAXE], *r;
    E *h[MAXN];
    void init(int n){
        memset(h, 0, sizeof(h[0])*(n+1));
        r = e;
    }
    void add(int u, int v){
        r->v = v;
        r->next = h[u];
        h[u] = r++;
    }
    int bfs(int a, int b){
        for(int i = 1; i <= b; ++i)
            for(int j = 1; j <= b; ++j)
                vi[i][j][0] = vi[i][j][1] = false;
        q[0] = Q(a, b, 0, 0);
        vi[a][b][0] = true;
        while(fr <= ba){
            Q t = q[fr++];
            if(t.a == b && t.b == a && t.c == 0)
                return t.d;
            if(t.c){
                for(E *i = h[t.b]; i; i = i->next)
                    if(!vi[t.a][i->v][0] && i->v != t.a){
                        q[++ba] = Q(t.a, i->v, 0, t.d+1);
                        vi[t.a][i->v][0] = true;
                        pre[t.a][i->v][0] = t.b;
                    }
            }else{
                for(E *i = h[t.a]; i; i = i->next)
                    if(!vi[i->v][t.b][1]){
                        q[++ba] = Q(i->v, t.b, 1, t.d+1);
                        vi[i->v][t.b][1] = true;
                        pre[i->v][t.b][1] = t.a;
                    }
            }
        }
        return -1;
    }
} g;

int p1[MAXN], p2[MAXN];
int main(){
    int n, m, u, v;
    scanf("%d%d", &n, &m);
    g.init(n);
    for(int i = 0; i < m; ++i){
        scanf("%d%d", &u, &v);
        g.add(u, v);
        g.add(v, u);
    }
    int ans = g.bfs(1, n);
    if(ans != -1){
        printf("%d
", ans/2);
        p1[ans/2] = n;
        p2[ans/2] = 1;
        int i1 = ans/2-1, i2 = ans/2-1;
        int a = n, b = 1, c = 0;
        for(int i = 0; i < ans; ++i){
            if(c){
                a = pre[a][b][c];
                p1[i1--] = a;
            }else{
                b = pre[a][b][c];
                p2[i2--] = b;
            }
            c ^= 1;
        }
        ans /= 2;
        for(int i = 0; i <= ans; ++i){
            if(i) printf(" ");
            printf("%d", p1[i]);
        }
        printf("
");
        for(int i = 0; i <= ans; ++i){
            if(i) printf(" ");
            printf("%d", p2[i]);
        }
        printf("
");
    }else
        printf("-1
");
    return 0;
}