bool spfa(){
	memset(in,0,sizeof(in));
	memset(vis,0,sizeof(vis));
	fill(d+1,d+1+n,-1.0);
	while(!q.empty()) q.pop();
	vis[1]=1;
	d[1]=1;//设定初始拥有钱数为1; 
	q.push(1);
	while(!q.empty()){
		int t = q.front();
		vis[t] = 0;//防止自环导致的错误，去掉后wa 
		for(int i=1;i<=n;i++){
			if(d[t]!=-1 && map[t][i]!=-1 && d[t]*map[t][i] > d[i]){
			//	debug(i);debug(t);debug(d[i]);debug(d[t]*map[t][i]);
				d[i] = d[t]*map[t][i];				
				if(!vis[i]){
					q.push(i);
					vis[i] = 1;
					in[i]++;
					if(in[i]>n){
						return true;
					}					
				}
			}
		}
		vis[t] = 0;
		q.pop();
	}
	return false;
}