ichirin2501's diary

いっちりーん。

AOJ :: 2107 :: Can I go there?

これ
http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=2107


問題概要

ある駅から駅に移動するのを1ステップとしたとき、スタート地点の駅からゴール地点の駅までちょうどZステップで行けるかどうか。
何度同じ駅を通っても良い。ただし、すぐに折り返すことはできない(A->B->Aのような移動は禁止されている)
駅(頂点)の個数は2個以上50個以下、区間(辺)の個数は1個以上50個以下、0


良問だと思う。




KステップでA地点からB地点まで行くパターン数を求めるのは、

重みなしグラフ G の隣接行列を A とすると、A^n で表される行列の (i, j) 成分は、i から j への相違なる長さ n の路の数と等しい

Wikiから引用。
行列のK乗で出来ることはわかっています。
今回はパターン数は必要ないので、隣接行列の(i,j)成分の計算は0か1の論理和で判定すれば良いことになります。
問題なのは、すぐに折り返すことができない、ということです。
どこから来たのか?と情報が必要になります。
(現在の駅、一つ前の駅)を、一つのノードとしてグラフを考えます。
駅の数が50個あるので、単純に考えると 2500個の状態ができてしまいます。
行列の掛け算の計算量は n^3 かかるので、とても間に合いません。
しかし、実際はノードの次数の合計数だけ考慮すればよく、区間数も50個以下なので状態数はM*2になります。
初期状態を考慮しても、状態数150を超えません。なんとか間に合います。


変換はこんな感じになります。
元の無向グラフ
画像1

0 1 1
1 0 1
1 1 0


(現在の駅、一つ前の駅)という状態を考えた有向グラフ

0 0 0 0 1 0
0 0 1 0 0 0
0 0 0 0 0 1
1 0 0 0 0 0
0 0 0 1 0 0
0 1 0 0 0 0
(0,1),(0,2),(1,0),(1,2),(2,0),(2,1)というノード順


スタート時のみ、どこでも行けるので初期ノードを追加する。

0 0 0 1 0 1 0
0 0 0 0 0 1 0
0 0 0 1 0 0 0
0 0 0 0 0 0 1
0 1 0 0 0 0 0
0 0 0 0 1 0 0
0 0 1 0 0 0 0
(0,0),(0,1),(0,2),(1,0),(1,2),(2,0),(2,1)というノード順


あとは、行列のZ乗を計算して、スタート地点からゴール地点まで行けるパターンがあったかどうかを調べればいい。

#include <vector>
#include <map>
#include <algorithm>
#include <iostream>
using namespace std;

#define REP(i,a,n) for(int i=(a); i<(int)(n); i++)
#define rep(i,n) REP(i,0,n)
#define all(x) (x).begin(),(x).end()
#define mp make_pair
#define pb push_back

int n,m,z,h;
int edge[64][64];
int edge2[200][200];
vector<pair<int,int> > v;

vector<int> calc(const vector<int>& a, const vector<int>& b){
	vector<int> ret;
	rep(i,h){
		rep(j,h){
			int sum = 0;
			rep(k,h){
				sum |= a[i*h+k]*b[k*h+j];
			}
			ret.pb(sum);
		}
	}
	return ret;
}

vector<int> multi(vector<int>& matrix, int k){
	if( k==1 ) return matrix;

	vector<int> tmp = multi(matrix,k/2);
	if( k%2 ){
		return calc(matrix,calc(tmp,tmp));
	}else{
		return calc(tmp,tmp);
	}
}

int main(){

	while(scanf(" %d%d%d ",&n,&m,&z),n|m|z){
		rep(i,64)rep(j,64)edge[i][j]=0;
		rep(i,200)rep(j,200)edge2[i][j]=0;
		
		v.clear();
		rep(i,m){
			int s,d; scanf("%d%d",&s,&d);
			edge[s][d] = edge[d][s] = 1;
		}
		
		edge[1][1] = 1;
		
		REP(i,1,n+1){
			REP(j,1,n+1)if( edge[j][i]==1 ){
				v.pb(mp(i-1,j-1));
			}
		}

		rep(i,v.size()){
			rep(j,v.size()){
				if( v[i].first!=v[j].first && v[i].first==v[j].second && v[i].second!=v[j].first ){
					edge2[i][j] = 1;
				}
			}
		}
		h = v.size();
		vector<int> mat;
		rep(i,v.size()){
			rep(j,v.size()){
				mat.pb(edge2[i][j]);
			}
		}

		vector<int> hoge = multi(mat,z);

		bool f = false;
		rep(i,v.size())if( v[i].first==n-1 ){
			if( hoge[i]>0 ){
				f = true;
				break;
			}
		}
		puts(f?"yes":"no");
	}
	return 0;
}