いろいろがんばりたいブログ

情報科学科の人がいろいろ書きます。

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;
}