AOJ 2107 Can I go there?
ノードを、前どこにいたかと、今どこにいるかのペアのようなものでつくる。 行列の累乗で計算する。 最初は、50*50 = 2500ノードで無理じゃんと思うけれど、よく見ると道の数が高々50なので、ノードの個数は高々100くらいなので大丈夫。
#include <iostream> #include <vector> #include <utility> #include <algorithm> #include <functional> #include <string> using namespace std; #define all(c) c.begin(),c.end() #define rep(i,n) for(int i=0;i<(int)n;i++) typedef long long ll; typedef vector<vector<ll> > ll_mat; namespace std{ ll_mat operator*(const ll_mat& lhs,const ll_mat& rhs){ int N = lhs.size(); ll_mat ret(N,vector<ll>(N)); for(int row=0;row<N;row++){ for(int col=0;col<N;col++){ for(int k=0;k<N;k++){ ret[row][col] += rhs[row][k] * lhs[k][col]; } } } return ret; } ostream& operator<<(ostream& os,ll_mat mat){ int N = mat.size(); for(int i=0;i<N;i++){ for(int j=0;j<N;j++){ os << mat[i][j] << " "; } os << endl; } return os; } ostream& operator<<(ostream& os,pair<int,int> p){ os << "<" << p.first << "," << p.second << ">"; return os; } }; ll_mat mat_pow(ll_mat x,ll n){ if(n == 0){ ll_mat E(x.size(),vector<ll>(x.size())); for(int i=0;i<x.size();i++){ E[i][i] = 1; } return E; }else{ ll_mat ret = mat_pow(x*x,n/2); if(n % 2 == 1) ret = ret * x; return ret; } } vector<ll> mat_multi(ll_mat lhs,vector<ll> rhs){ vector<ll> ret(rhs.size()); int N = lhs.size(); for(int i=0;i<N;i++){ for(int j=0;j<N;j++){ ret[i] += lhs[i][j] * rhs[j]; } } return ret; } int main(){ while(true){ int N,M; ll Z; cin >> N >> M >> Z; if(N == 0 and M == 0 and Z == 0) break; // now , from vector<pair<int,int> > nodes; // start node. nodes.push_back(make_pair(1,0)); for(int i=0;i<M;i++){ int from,to; cin >> from >> to; nodes.push_back(make_pair(to,from)); nodes.push_back(make_pair(from,to)); } int NODES_SIZE = nodes.size(); ll_mat dist(NODES_SIZE,vector<ll>(NODES_SIZE)); for(int i=0;i<NODES_SIZE;i++){ int now = nodes[i].first; int from = nodes[i].second; for(int j=0;j<NODES_SIZE;j++){ if(i == j) continue; int new_now = nodes[j].first; int new_from = nodes[j].second; if(now == new_now) continue; if(new_now == from) continue; if(now == new_from){ dist[j][i] = 1; } } } // cerr << dist << endl; // for(int i=0;i<NODES_SIZE;i++){ // cerr << nodes[i] << endl; // } vector<ll> start_mat(NODES_SIZE); start_mat[0] = 1; ll_mat powed = mat_pow(dist,Z); //cerr << "powed" << endl << powed << endl; vector<ll> finally = mat_multi(powed,start_mat); bool ok = false; for(int i=0;i<NODES_SIZE;i++){ //cerr << finally[i] << endl; if(nodes[i].first == N and finally[i] != 0){ ok = true; } } if(ok){ cout << "yes" << endl; }else{ cout << "no" << endl; } } return 0; }