http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2107
頂点を行列にするとうまく行かなくて、辺を行列にするといい。すなわち
ある辺のうちどっちにいるかを値にして、次どこ行けるのか行列で持てば良い。
最初の1回はどこにもいけるので特別な辺を貼って対処する。
ほとんどデバッグしないで通ったのでいいね。
int N, M, Z; int E[60][2]; void solve_sub() { mat A(M * 2, vl(M * 2, 0)); rep(i, 0, M) { rep(j, 0, 2) { int v = E[i][j]; int id = i * 2 + j; rep(k, 0, M) { if(i == k) continue; if(E[k][0] == v) { int tid = k * 2 + 1; A[tid][id] = 1; } else if(E[k][1] == v) { int tid = k * 2; A[tid][id] = 1; } } } } //rep(i, 0, sz(A)) debug(A[i]); mat B = mat_pow(A, Z); rep(i, 0, M) { rep(j, 0, 2) { int id = i * 2 + j; if(E[i][j] == N - 1) { if(B[id][2 * M - 2]) { cout << "yes\n"; return; } } } } cout << "no\n"; } void solve() { while(true) { cin >> N >> M >> Z; if(N == 0 && M == 0 && Z == 0) return; memset(E, 0, sizeof(E)); rep(i, 0, M) { int a, b; cin >> a >> b; a--; b--; E[i][0] = a; E[i][1] = b; } E[M][0] = 0; E[M][1] = N + 1; M++; solve_sub(); } }