学步园

　　As we all know, KRH lives in SCNU as a god. We always meet him in dining hall, or in training room, or in college building, or in front of the dormitory, even on a side road. Evil smile is always shown on his face. That\'s terrible, so a
retired ACMer, LiJunLe decides to track him.
　　LiJunLe finds that, KRH starts strolling from the dining hall every time. When he runs out of his power, he will stop here and not go any more. That is, the distance he walks pass relates with how many calories KRH gets in dinner.
　　Today, LiJunLe stays in his dormitory, West 2. As you know, the dormitory West 2 is older than most of students in SCNU. That is a legend! It is founded in 1986, so far to stand for more than 20 years. Besides friendly mice, crouching tigers and hidden dragon
are also living in West 2 dormitory. Seen from the photo below, The dormitory locates at good position, provides reasonable layout, has well equipments and uses advanced management solution. The dormitory is only for our South China Normal School students.
It is a real ideal place for living and studying!
　　
　　But now, LiJunLe is bored, and think whether KRH will stop at West 2 or not. He wants to know what is the probability?
　　To simplify the problem, suppose the map of SCNU is an undirected graph. Suppose each building as a node, and the distance between two building is one unit of length. If KRH gets one unit of calories, he can walk exactly one unit of length.By
the way, KRH will not hang around the street.
　　When KRH reaches a building, he will choose any one road randomly. It means that the probability of selecting any road is absolutely equal.
　　There are n buildings in SCNU. The node index of the dining hall is always 1, and West 2 dormitory is always 2.

　　The first line is a number T (1<=T<=30), indicating the number of test cases below.
　　In each test case, two numbers, n (2<=n<=200), m (1<=m<=30000) and k (1<=k<=50000) are displayed. The number n indicates the number of buildings in SCNU, m indicates the number of roads in SCNU, and k indicates the calories KRH gets before strolling.
　　Then, m lines follow. Each line contains two numbers, a and b (1<=a,b<=n, a!=b), indicates building with number a and b are connected by a road.

　　One line for one test case, containing "Case #D: E". "D" is the index of the test case, starting from 1, and "E" is the probability LiJunLe wants, corrects to 0.0001.

3
2 1 1
1 2
3 2 2
3 1
2 3
3 1 5
1 3

Case #1: 1.0000
Case #2: 0.5000
Case #3: 0.0000

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

int n,k;
double rec[210][210];
double ans[210][210];

void Mul(double a[][210],double b[][210])//矩阵乘法  使得a=a*b  
{
	double c[210][210];
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
		{
			double sum=0;
			for(int k=1;k<=n;k++)
				sum+=a[i][k]*b[k][j];
			c[i][j]=sum;
		}
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			a[i][j]=c[i][j];
}

void Pow()
{
	for(int i=1;i<=n;i++)//构造单位矩阵 
		for(int j=1;j<=n;j++)
			ans[i][j]=(i==j);
	while(k)//非递归快速幂 用递归会暴栈 
	{
		if(k&1)
			Mul(ans,rec);
		Mul(rec,rec);
		k>>=1;
	}
}

int main()
{
	int t;
	int cnt=1;
	int m;
	scanf("%d",&t);
	while(t--)
	{
		scanf("%d%d%d",&n,&m,&k);
		vector<int> g[210];
		for(int i=1;i<=m;i++)
		{
			int x,y;
			scanf("%d%d",&x,&y);
			g[x].push_back(y);
			g[y].push_back(x);
		}
		memset(rec,0,sizeof(rec));
		for(int i=1;i<=n;i++)//构造概率矩阵 
		{
			int sz=g[i].size();
			if(sz==0)
				continue;
			for(int j=0;j<sz;j++)
				rec[i][g[i][j]]+=1.0/sz;
		}
		Pow();//进行矩阵快速幂 
		printf("Case #%d: %.4lf\n",cnt++,ans[1][2]);
	}
	return 0;
}