高斯消元又弄了半天。。
注意只要能建立矩阵,那就必定有解,所以高斯消元里可以直接return 1
#include<bits/stdc++.h> using namespace std; const int maxn = 205; const double esp = 1e-7; int n,m,x,y,d; double p[maxn],a[maxn][maxn],b[maxn]; int equ,var; int Gauss(){ for(int i=0;i<n;i++){ int maxr=i; for(int j=i+1;j<n;j++) if(fabs(a[j][i])>fabs(a[maxr][i])) maxr=j; if(fabs(a[maxr][i])<esp)continue; if(maxr!=i) swap(a[maxr],a[i]);swap(b[maxr],b[i]); for(int j=i+1;j<n;j++){ if(fabs(a[j][i])<esp)continue; double rate=a[j][i]/a[i][i]; for(int k=i;k<n;k++) a[j][k]-=rate*a[i][k]; b[j]-=rate*b[i]; } } for(int i=n-1;i>=0;i--){ if(fabs(a[i][i])<esp)continue; for(int j=i+1;j<n;j++) b[i]-=a[i][j]*b[j]; b[i]/=a[i][i]; } return 1; } int id[maxn],cnt; void bfs(int s){ memset(id,-1,sizeof id); cnt=0; queue<int>q; q.push(s);id[s]=cnt++; while(q.size()){ int x=q.front();q.pop(); for(int i=1;i<=m;i++){ if(fabs(p[i])<esp)continue; int y=(x+i)%n; if(id[y]==-1) q.push(y),id[y]=cnt++; } } } int main(){ int t;cin>>t; while(t--){ scanf("%d%d%d%d%d",&n,&m,&y,&x,&d); for(int i=1;i<=m;i++) scanf("%lf",&p[i]),p[i]/=100; if(x==y){puts("0.00");continue;} n=2*(n-1); if(d==1)x=n-x; bfs(x); if(id[y]==-1 && id[n-y]==-1){ puts("Impossible !");continue; } equ=var=cnt; memset(a,0,sizeof a); memset(b,0,sizeof b); for(int i=0;i<n;i++){ if(id[i]==-1)continue; a[id[i]][id[i]]=1; if(i==y || i==n-y)continue;//到了终点y for(int j=1;j<=m;j++){ int y=(i+j)%n; if(id[y]!=-1){ a[id[i]][id[y]]-=p[j]; b[id[i]]+=j*p[j]; } } } if(Gauss()) printf("%.2lf\n",b[id[x]]); else printf("Impossible !\n"); } }