代码

#include<iostream>
#include<cstdio>
#include<climits>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
int T,tot,n,m,v,u,d;
int g[205],q[205];
double p[205],a[205][205],eps=1e-6;
void bfs(){
int i,he=1,ta=1,to;
q[he]=u;g[u]=tot++;
while(he<=ta){
for(i=1;i<=m;i++){
if(fabs(p[i])<eps)continue;
to=(q[he]+i)%n;
if(g[to]==-1){g[to]=tot++;q[++ta]=to;}
}
he++;
}
}
bool guss(){
int i,j,k,bj;double t;
for(k=0;k<tot;k++){
bj=k;
for(i=k+1;i<tot;i++)
if(fabs(a[i][k])>fabs(a[bj][k]))bj=i;
if(fabs(a[bj][k])<eps)return 0;
if(bj!=k)for(j=k;j<=tot;j++)swap(a[k][j],a[bj][j]);
t=a[k][k];
for(j=k;j<=tot;j++)a[k][j]/=t;
for(i=0;i<tot;i++)if(i!=k){
if(fabs(a[i][k])<eps)continue;
t=a[i][k];
for(j=k;j<=tot;j++)a[i][j]-=t*a[k][j];
}
}
return 1;
}
int main()
{
int i,j;
scanf("%d",&T);
while(T--){
scanf("%d%d%d%d%d",&n,&m,&v,&u,&d);
for(i=1;i<=m;i++){scanf("%lf",&p[i]);p[i]/=100.0;}
if(u==v){printf("0.00\n");continue;}
n=n*2-2;if(d==1&&u!=0)u=n-u;
for(i=0;i<n;i++)g[i]=-1;
tot=0;bfs();
if(g[v]==-1&&g[n-v]==-1){printf("Impossible !\n");continue;}
memset(a,0,sizeof(a));
for(i=0;i<n;i++){
if(g[i]==-1)continue;
a[g[i]][g[i]]=1.0;
if(i==v||i==n-v)continue;
for(j=1;j<=m;j++){
if(fabs(p[j])<eps)continue;
int to=(i+j)%n;
if(g[to]==-1)continue;
a[g[i]][g[to]]-=p[j];a[g[i]][tot]+=p[j]*j;
}
}
if(!guss()){printf("Impossible !\n");continue;}
printf("%.2lf\n",a[g[u]][tot]);
}
return 0;
}