记录编号	457102	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[東方S3] 铃仙•优昙华院•稻叶	最终得分	100
用户昵称	하루Kiev	是否通过	通过
代码语言	C++	运行时间	0.985 s
提交时间	2017-10-06 19:39:59	内存使用	11.98 MiB

# include "iostream"
# include "stdio.h"
# include "algorithm"
# include "string.h"
# include "math.h"
using namespace std;
int n,m,t,map[55][55],dg[55],ai,bi;
double f[505][55][55];
bool flag;
//f[i][j][k] 第i个时间单位 由k路口走到j路口的概率
//f[i][j][k]=sigma f[i-1][k][除了j连向k的点] 
int main(){
	freopen("reisen.in","r",stdin);
	freopen("reisen.out","w",stdout);
	scanf("%d%d%d",&n,&m,&t);
	for(int i=1;i<=m;i++){
		scanf("%d%d",&ai,&bi);
		map[ai][bi]=1;
		dg[ai]++;
	}
	f[0][1][1]=1.00;
	for(int i=0;i<=t;i++)
	    for(int j=1;j<=n;j++)
	    	for(int k=1;k<=n;k++)
	    		if(f[i][j][k]>0.0){
	    		   for(int o=1;o<=n;o++)
	    		   	   if((map[j][o]&&o!=k)){					  
	    		   	      if(map[j][k]) f[i+1][o][j]+=f[i][j][k]*1.00/(dg[j]);
	    		   	      else f[i+1][o][j]+=f[i][j][k]*1.00/(dg[j]+1);
	    		   	    }
	    		   	if(map[j][k]) f[i+1][j][k]+=f[i][j][k]*1.00/(dg[j]);
				    else f[i+1][j][k]+=f[i][j][k]*1.00/(dg[j]+1);
				}	
	for(int i=1;i<=n;i++){
		double ans=0.0;
		for(int j=1;j<=n;j++)
		    ans+=f[t][i][j];
		printf("%.3lf\n",ans*100);
	}	
}
/*
3 4 2
1 2
1 3
2 1
2 3
*/
/*
11.111
27.778
61.111
*/