AOJ-2107 : Can I go there? (いけるかな？)

問題概要

ノード数N(<50)、辺数M(<50)の無向グラフがある。0からN-1への長さZ(<2^31)の経路が存在するか求める問題。ただし同じ辺を連続で使用することはできない。

解法

(直前に居た頂点、今いる頂点)を組にしたグラフを考える。後は行列累乗で計算するだけ。最初見たときはM<50に気づかなかった…。

acceptされたコード

計算量O(M^3 * log Z)。

#include <cstdio>
#include <vector>
#include <cstring>
using namespace std;

typedef bool mat_t;

struct matrix{

	vector< vector<mat_t> > val;
	int height, width;

	matrix(){}
	matrix(int height_, int width_):height(height_), width(width_){
		val.assign(height, vector<mat_t>(width, false));
	}

	vector<mat_t>& operator[](const size_t ind){
		return val[ind];
	}
};

matrix get_identity(int size){
	matrix ret(size, size);
	for(int i=0; i<size; i++){
		ret[i][i] = true;
	}
	return ret;
}

matrix operator*(const matrix& lhs, const matrix& rhs){
	matrix ret(lhs.height, rhs.width);

	for(int i=0; i<lhs.height; i++){
		for(int k=0; k<lhs.width; k++){
			for(int j=0; j<rhs.width; j++)if(lhs.val[i][k] && rhs.val[k][j]){
				ret[i][j] = true;
			}
		}
	}

	return ret;
}

matrix pow(const matrix& x, const int k){
	matrix ret = get_identity(x.width), base = x;

	for(int e=k; e; e>>=1){
		if(e&1){
			ret = ret * base;
		}
		base = base * base;
	}


	return ret;
}

const int MAX_N = 50;
const int MAX_M = 50;

int N, M, Z;

pair<int,int> edge[2*MAX_M];
bool after[2*MAX_M], result[2*MAX_M];

bool init(){
	scanf("%d%d%d", &N, &M, &Z);
	for(int i=0; i<M; i++){
		int x, y;
		scanf("%d%d", &x, &y);
		x--; y--;
		edge[2*i + 0] = make_pair(x, y);
		edge[2*i + 1] = make_pair(y, x);
	}
	return N > 0;
}

bool solve(){
	matrix mat(2*M, 2*M);
	for(int i=0; i<2*M; i++){
		for(int j=0; j<2*M; j++)if(i!=j){
			if(edge[i].second == edge[j].first && edge[i].first != edge[j].second){
				mat[i][j] = true;
			}
		}
	}
	mat = pow(mat, Z-1);

	memset(after, false, sizeof(after));
	for(int i=0; i<2*M; i++){
		if(edge[i].first == 0){
			after[i] = true;
		}
	}

	memset(result, false, sizeof(result));
	for(int i=0; i<2*M; i++){
		for(int j=0; j<2*M; j++){
			result[j] |= mat[i][j] && after[i];
		}
	}

	for(int i=0; i<2*M; i++)if(result[i] && edge[i].second == N-1){
		return true;
	}

	return false;
}

int main(){
	for(;init();){
		puts(solve() ? "yes" : "no");
	}

	return 0;
}