记录编号	92711	评测结果	AAAAAAAAAA
题目名称	考验	最终得分	100
用户昵称	digital-T	是否通过	通过
代码语言	C++	运行时间	0.007 s
提交时间	2014-03-22 11:00:59	内存使用	0.31 MiB

#include<fstream>
#include<vector>
using namespace std;
ifstream fi("testz.in");
ofstream fo("testz.out");
int n;
long long ans=1;
vector <pair<int,int> > way[26];
bool boo[26]={false};
long long gcd(long long x,long long y){
return y==0?x:gcd(y,x%y);}

void dfs(int x,long long fee)
{
	if(x==2)
	{
		int tmp;
		tmp=gcd(ans,fee);
		ans/=tmp;
		ans*=fee;
		return;
	}
	if(ans%fee==0)return;
	for(int k=0;k<way[x].size();k++)
		if(!boo[way[x][k].first])
		{
			boo[way[x][k].first]=true;
			dfs(way[x][k].first,gcd(way[x][k].second,fee));
			boo[way[x][k].first]=false;
		}
}
int main()
{
	fi>>n;
	int i,j,t;
	for(i=1;i<=n;i++)
		for(j=1;j<=n;j++)
		{
			fi>>t;//从i区域到j区域的路径长度,不连通则为0
			if(t!=0)way[i].push_back(make_pair(j,t));
		}
	boo[1]=true;
	for(i=0;i<way[1].size();i++)
	{
		boo[way[1][i].first]=true;
		dfs(way[1][i].first,way[1][i].second);
		boo[way[1][i].first]=false;
	}
	fo<<ans<<endl;
	return 0;
}