一个数据包在一个无向网络中传递。在时刻0，该数据包将依照特定的概率随机抵达网络中的某个节点。
网络可以看做一张完全带权无向图，包含N个节点，若t时刻数据包在节点i，则在t+1时刻，数据包被传递到节点j的概率是
d(i,j)/(∑kd(i,k))
其中d(i,j)表示节点i到节点j的最短路径的长度。在传递到下一个节点后，该数据包会自动删除在当前节点的备份。
现在，给定数据包0时刻在每个节点的概率和网络的每条边权。求T时刻数据包在每个节点的概率。
输入格式
第一行两个整数N和T。
第二行N个实数，表示0时刻数据包在每个节点的概率（保证概率加起来为1）。
接下来N行每行N个整数,第i行第j个数表示节点i和节点j之间的边权。
保证第i行第i个数为0且第i行第j个数等于第j行第i个数。
输出格式
输出共N行，第i行表示T时刻数据包在节点i的概率，保留六位小数。
数据范围与约定
对于50%的数据，T≤20。
对于100%的数据,N≤200,T≤10^9。保证对于每个点d的和值在int范围。
样例输入
3 2
0 1 0
0 1 4
1 0 2
4 2 0
样例输出
0.400000
0.350000
0.250000
首先列出dp式
f[t][v]=∑uf[t-1][u]*(d(u,v)/(∑kd(u,k)))
显然含有矩阵快速幂的特点，写出矩阵，假设n=3
0 d(1,2)/(∑kd(1,k)) d(1,3)/(∑kd(1,k))
d(2,1)/(∑kd(2,k)) 0 d(2,3)/(∑kd(2,k))
d(3,1)/(∑kd(3,k)) d(3,2)/(∑kd(3,k)) 0
d的话直接弗洛伊德
转移矩阵Mat[i][j]=d(i,j)/(∑kd(i,k))
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
struct Matrix
{
double a[][];
}Mat,pre,st,ans;
int n,T;
double s[],map[][];
Matrix operator *(const Matrix &x,const Matrix &y)
{
Matrix res;
int i,j,k;
memset(res.a,,sizeof(res.a));
for (i=;i<=n;i++)
{
for (j=;j<=n;j++)
{
for (k=;k<=n;k++)
{
res.a[i][j]+=x.a[i][k]*y.a[k][j];
}
}
}
return res;
}
void qpow(int x)
{int i;
for (i=;i<=n;i++)
ans.a[i][i]=;
while (x)
{
if (x&) ans=ans*Mat;
Mat=Mat*Mat;
x/=;
}
}
int main()
{int i,j,k;
cin>>n>>T;
memset(pre.a,,sizeof(pre.a));
memset(Mat.a,,sizeof(Mat.a));
for (i=;i<=n;i++)
scanf("%lf",&pre.a[][i]);
for (i=;i<=n;i++)
{
for (j=;j<=n;j++)
{
scanf("%lf",&map[i][j]);
}
}
for (k=;k<=n;k++)
for (i=;i<=n;i++)
if (i!=k)
for (j=;j<=n;j++)
if (i!=j&&k!=j)
map[i][j]=min(map[i][j],map[i][k]+map[k][j]);
for (i=;i<=n;i++)
for (j=;j<=n;j++)
if (i!=j) s[i]+=map[i][j];
for (i=;i<=n;i++)
{for (j=;j<=n;j++)
if (i!=j)
Mat.a[j][i]=map[j][i]/s[j];
}
qpow(T);
ans=pre*ans;
for (i=;i<=n;i++)
printf("%.6lf\n",ans.a[][i]);
}