把N个点先转化为2*N-2个点。
比如说把012345转化成0123454321。
这样,就可以找出任意两两个点之间的关系。
然后根据关系可以得出来一个一元多项式的矩阵。
然后就用高斯消元求出矩阵即可。
#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
#include<queue>
#include<math.h>
using namespace std;
#define eps 1e-6
#define zero(x) ((fabs(x)<eps?0:x))
#define maxn 220
double a[maxn][maxn];
int g[maxn],cnt;
int n,m,st,ed;
double p[maxn];
int guss(int n)
{int r;for(int i=0;i<n;i++){r=i;for(int j=i+1;j<n;j++){if(fabs(a[j][i])>fabs(a[r][i]))r=j;}if(!zero(a[r][i]))return 0;if(r!=i){for(int j=0;j<=n;j++)swap(a[i][j],a[r][j]);}for(int j=i+1;j<=n;j++)a[i][j]/=a[i][i];a[i][i]=1.0;for(int j=0;j<n;j++){if(j==i)continue;for(int k=i+1;k<=n;k++){a[j][k]-=a[i][k]*a[j][i];}a[j][i]=0;}}return 1;
}
void bfs()
{queue<int>que;while(!que.empty())que.pop();que.push(st);memset(g,-1,sizeof(g));cnt=0;g[st]=cnt++;while(!que.empty()){int x=que.front();que.pop();for(int i=1;i<=m;i++){if(!zero(p[i]))continue;int y=(i+x)%n;if(g[y]==-1){g[y]=cnt++;que.push(y);}}}
}
int main()
{int T,d;scanf("%d",&T);while(T--){scanf("%d%d%d%d%d",&n,&m,&ed,&st,&d);for(int i=1;i<=m;i++){scanf("%lf",&p[i]);p[i]=1.0*p[i]/100.0;}if(ed==st){puts("0.00");continue;}n=2*n-2;if(d==1)st=n-st;bfs();if(g[ed]==-1&&g[n-ed]==-1){puts("Impossible !");continue;}memset(a,0,sizeof(a));for(int i=0;i<n;i++){if(g[i]==-1)continue;if(i==ed||i==n-ed){a[g[i]][g[i]]=1;a[g[i]][cnt]=0;continue;}a[g[i]][g[i]]=1.0;for(int j=1;j<=m;j++){int y=(i+j)%n;if(g[y]==-1)continue;a[g[i]][g[y]]-=p[j];a[g[i]][cnt]+=1.0*j*p[j];}}if(!guss(cnt))puts("Impossible !");else printf("%.2lf\n",a[g[st]][cnt]);}return 0;
}