设$f[x][y]$表示从x和y出发相遇的期望长度，则$f[x][x]=0$，且$f[x][y]$对称，共$C(n,2)$个未知量。

列出方程组$G$，得到$G\times F=B$。

高斯消元求出$G$的逆矩阵$G'$，则$F=G'\times B$，对于每个询问代入计算即可。

时间复杂度$O(n^6+tn^4)$。

 

#include
     
      #include
      
       #include
       
        using namespace std;const int N=235;int n,m,T,i,j,k,x,y,o,id[25][25],cnt,d[25],e[25][25];double p[25],f[N][N],g[N][N],B[N][N],len[N],t,ans;int main(){  scanf("%d%d%d",&n,&m,&T);  for(i=1;i<=n;i++)for(j=1;j<=n;j++)e[i][j]=-1;  for(i=1;i<=n;i++)e[i][i]=0;  for(i=1;i<=m;i++){    scanf("%d%d",&x,&y);    d[x]++,d[y]++;    e[x][y]=e[y][x]=i;  }  for(i=1;i<=n;i++)scanf("%lf",&p[i]);  for(i=1;i<=n;i++)for(j=i+1;j<=n;j++)id[i][j]=++cnt;  for(i=1;i<=n;i++)for(j=i+1;j<=n;j++){    o=id[i][j];    f[o][o]=1;    for(x=1;x<=n;x++)if(~e[i][x])for(y=1;y<=n;y++)if(~e[j][y]){      t=1;      if(x==i)t*=p[i];else t*=(1.0-p[i])/d[i];      if(y==j)t*=p[j];else t*=(1.0-p[j])/d[j];      B[o][e[i][x]]+=t;      B[o][e[j][y]]+=t;      if(x!=y)f[o][x
        
         fabs(f[k][i]))k=j;    if(k!=i)for(j=1;j<=cnt;j++)swap(f[i][j],f[k][j]),swap(g[i][j],g[k][j]);    for(j=i+1;j<=cnt;j++)for(t=f[j][i]/f[i][i],k=1;k<=cnt;k++)f[j][k]-=f[i][k]*t,g[j][k]-=g[i][k]*t;  }  for(i=cnt;i;i--){    for(j=cnt;j>i;j--)for(t=f[i][j],k=1;k<=cnt;k++)f[i][k]-=f[j][k]*t,g[i][k]-=g[j][k]*t;    for(t=f[i][i],j=1;j<=cnt;j++)f[i][j]/=t,g[i][j]/=t;  }  while(T--){    for(i=1;i<=m;i++)scanf("%lf",&len[i]);    scanf("%d%d",&x,&y);    if(x==y){puts("0.00");continue;}    o=x