codeforces 601A(腦筋急轉彎 ， 55)

題目意思，給了最多400個點的完全圖，但是每條邊可能是公路也可能是鐵路，求1個火車和一個汽車同時都從1出發到n中間不走到重複點的最短時間.

1 - n 這條邊必定是鐵路或公路，然後就沒有然後了。

下面是自己傻X用壓縮了一下轉移寫的。直接輛車出發最短時間到n 的最小值即答案、

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
#define clr(a , x) memset(a , x , sizeof(a))
#define rep(i , n) for(int i=0;i<(int)n ; i++)
#define rep1(j , x , y) for(int j=(int)x;j<=(int)y;j++)
#define repd(j , y , x) for(int j=(int)y;j>=(int)x;j--)

const int inf = 1e7;
const int N = 410;
int vis[N][N];
vector<int> G[2][N];
int dis[2][N],d[N][N][2];
struct node{
   int x , y, dir;
   node(){}
   node(int x , int y,int dir):x(x) , y(y),dir(dir){}
};
int n, m;
int bfs() {
    rep(i , 2){
         queue<int> Q;
         clr(dis[i], -1);
         dis[i][n] = 0;
         Q.push(n);
         while(!Q.empty()){
              int u = Q.front() ; Q.pop();
              for(auto v : G[i][u]){
                   if(dis[i][v] == -1){
                        dis[i][v] =  dis[i][u] + 1;
                        Q.push(v);
                   }
              }
         }
    }
    int ans = inf;
    clr(d , -1);
    queue<node> Q;
    d[1][1][0] = 0;
    Q.push(node(1 , 1 , 0));
    while(!Q.empty()){
        node u = Q.front(); Q.pop();
        int x = u.x , y = u.y  , dir = u.dir;
        if(u.x == n || u.y == n){
              ans = min(ans , d[x][y][dir]/2 + (x==n ? (dis[1][y] == -1 ? inf : dis[1][y]) : (dis[0][x] == -1 ? inf : dis[0][x])));
              continue;
        }
             if(dir == 0){
                 for(auto i : G[dir][x]){
                   if(d[i][y][1] == -1)
                       d[i][y][1] = d[x][y][dir] + 1 , Q.push(node(i , y , 1));
                 }
             } else {
                for(auto i : G[dir][y]) if(i != x && i!=y){
                  if(d[x][i][0] == -1)
                       d[x][i][0] = d[x][y][dir] + 1 , Q.push(node(x , i , 0));
                }
             }
    }
    return ans==inf ? -1 : ans;
}
int main()
{
   while(scanf("%d %d",&n,&m)==2){
       rep1(i , 1 , m){
           int u , v;
           scanf("%d %d",&u ,&v);
           vis[u][v] = vis[v][u] = 1;
           G[0][u].push_back(v);
           G[0][v].push_back(u);
       }
       rep1(i ,1 , n) rep1(j, 1 , n)
           if(i != j && !vis[i][j]) G[1][i].push_back(j);
       cout<<bfs()<<endl;
   }
   return 0;
}