这题主要有两种做法：1种是用逆矩阵，转移时无须高斯消元。2是将常数项回代。这里主要介绍第一种。
首先题里少个条件：点权非负。设f [ i ][ j ]表示hp为i时，到达j点的期望次数。
那么若点权为正，直接转移：f [ i + w[ j ] ][ i ]对f [ i ][ j ]的贡献为f[ i+w[j] ]/d[ i ]（d[i]表示点i的出度）
若点权为0，则需高斯消元，单次消元复杂度（n^3）显然会炸，我们考虑优化。、
对于高斯消元，有一个结论：系数矩阵*答案矩阵=常数矩阵（用方程组的定义来理解，挺简单的，虽然我想了好久）
将系数矩阵换到右边，就变成了 答案矩阵=常数矩阵×系数矩阵的逆
对于本题而言，系数矩阵是不变的，变化的只有常数矩阵，而常数矩阵O（m）即可处理出，因此我们可以预处理出系数矩阵的逆矩阵,之后每次只需将逆矩阵与常数矩阵相乘，而常数矩阵为一个列向量，每次乘法复杂度O（n^2）,总复杂度O（(n^2+m)hp+n^3）。
对于矩阵求逆只需将原矩阵高斯消元，然后不管什么操作都对一个单位矩阵做同等变换，单位矩阵在消完元后也就变成了原矩阵的逆矩阵。
1 #include<bits/stdc++.h> 2 #define eps 1e-8 3 using namespace std; 4 int n,m,hp,a[155],tot,to[10005],fi[155],ne[10005],du[155]; 5 double c[155][155],b[155][155],d[155][155],f[10005][152],dp[152],ans; 6 inline void add(int x,int y) 7 { 8 ne[++tot]=fi[x]; 9 fi[x]=tot; 10 to[tot]=y; 11 } 12 int main() 13 { 14 scanf("%d%d%d",&n,&m,&hp); 15 for(int i=1;i<=n;i++) 16 scanf("%d",&a[i]); 17 for(int i=1,x,y;i<=m;i++) 18 { 19 scanf("%d%d",&x,&y); 20 add(x,y),du[x]++; 21 if(x!=y) 22 add(y,x),du[y]++; 23 } 24 for(int i=1;i<n;i++) 25 for(int j=fi[i];j;j=ne[j]) 26 { 27 int y=to[j]; 28 if(!a[y]) 29 { 30 c[y][i]+=1.0/du[i]; 31 } 32 } 33 for(int i=1;i<=n;i++) 34 b[i][i]=1,c[i][i]--; 35 for(int i=1;i<=n;i++) 36 { 37 int k=i; 38 for(int j=i+1;j<=n;j++) 39 if(fabs(c[j][i])>fabs(c[k][i])) 40 k=j; 41 for(int j=1;j<=n;j++)swap(c[i][j],c[k][j]),swap(b[i][j],b[k][j]); 42 if(fabs(c[i][i])<eps)continue; 43 double r=c[i][i]; 44 for(int j=1;j<=n;j++) 45 c[i][j]/=r,b[i][j]/=r; 46 for(int j=1;j<=n;j++) 47 { 48 if(i==j)continue; 49 double r=c[j][i]; 50 for(int k=1;k<=n;k++) 51 c[j][k]-=r*c[i][k],b[j][k]-=r*b[i][k]; 52 } 53 } 54 f[hp][1]=-1; 55 for(int i=hp;i;i--) 56 { 57 for(int j=1;j<=n;j++) 58 for(int k=1;k<=n;k++) 59 dp[j]+=f[i][k]*b[j][k]; 60 ans+=dp[n]; 61 for(int j=1;j<n;j++) 62 { 63 for(int k=fi[j];k;k=ne[k]) 64 { 65 int y=to[k]; 66 if(a[y]&&i>a[y]) 67 f[i-a[y]][y]-=1.0*dp[j]/du[j]; 68 } 69 dp[j]=0; 70 } 71 dp[n]=0; 72 } 73 printf("%.8lf",ans); 74 return 0; 75 }