Codeforces #333 Div1 A. The Two Routes

ABC解けたもののミスしまくりで微妙な順位。挙句の果てに問題見てないDの方がBCより簡単だったし…。
http://codeforces.com/contest/601/problem/A

問題

1～Nの番号を町がある。
2つの町の間は鉄道かバスのどちらかが走っている。それらの移動時間はともに１である。

1番からN番の町に、鉄道だけ、またはバスだけで移動したいまた、両移動経路において、(1,N番の町以外で)同時刻に同じ町にいてはならない。
鉄道・バスどちらでも到達可能な場合、両経路で移動する最短経路を求めよ。

解法

2つの町の間は鉄道かバスかどちらかは利用可能なので、1番からN番に鉄道かバスどちらかは直結する経路がある。
よって、直結しない方の交通機関についてWarshall-Floyedなりなんなりで最短経路を求めればよい。

int N,M;
int mat[401][401];

void solve() {
	int i,j,k,l,r,x,y,z; string s;
	
	cin>>N>>M;
	FOR(x,N) FOR(y,N) if(x!=y) mat[x][y]=1010;
	
	FOR(i,M) {
		cin>>x>>y;
		mat[x-1][y-1]=mat[y-1][x-1]=1;
	}
	if(mat[0][N-1]==1) {
		FOR(x,N) FOR(y,N) if(x!=y) mat[x][y]=(mat[x][y]==1)?1010:1;
	}
	
	FOR(z,N) FOR(x,N) FOR(y,N) mat[x][y]=min(mat[x][y],mat[x][z]+mat[z][y]);
	
	if(mat[0][N-1]>1000) return _P("-1\n");
	_P("%d\n",mat[0][N-1]);
	
}

まとめ

本番は両者それぞれWFやったうえ、同じ点を同時に通ることがないか無駄チェックしてしまった。
片方は一手でゴールにつくのにね…。