Problem 2107 : Can I go there?

問題概要

日本語なので略。
本文参照（http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=2107&lang=jp）

解法

現在どのノードにいるか、直前にどのノードにいたかを(i,j)とあらわす。
この状態数は辺の数×2になる。

（辺×2）×（辺×2）のグラフを考える。
i!=kで、jからkへの辺があるとき、(i,j)→(j,k)の辺を貼る。
このような行列のn乗を考えればよい。

ただし初期状態として(0,0)などを用意しておく必要がある。
(0,0)へ入る辺はなくしておく。

ソースコード

int n,m,g,z;
vector<pi> e;
int f[111][111],ans[111][111],t[111][111];

void prod(int a[111][111],int b[111][111])
{
	rep(i,n)rep(j,n)
	{
		t[i][j]=0;
		rep(k,n)if(a[i][k]&&b[k][j])
		{
			t[i][j]=1; goto NEXT;
		}
		NEXT:;
	}
	rep(i,n)rep(j,n)a[i][j]=t[i][j];
}
int main()
{
	while(scanf("%d%d%d",&g,&m,&z),g)
	{
		e.clear();
		e.pb(mp(0,0));
		rep(i,m)
		{
			int a,b; scanf("%d%d",&a,&b);
			e.pb(mp(a-1,b-1)); e.pb(mp(b-1,a-1));
		}
		n=2*m+1;
		rep(i,n)rep(j,n)f[i][j]=j>0&&e[i].second==e[j].first&&e[i].first!=e[j].second;
		rep(i,n)rep(j,n)ans[i][j]=i==j;
		for(;z>0;z/=2)
		{
			if(z&1)prod(ans,f);
			prod(f,f);
		}
		rep(i,n)if(e[i].second==g-1&&ans[0][i])
		{
			puts("yes"); goto END;
		}
		puts("no"); END:;
	}
	return 0;
}