把N個點先轉化為2*N-2個點。
比如說把012345轉化成0123454321。
這樣，就可以找出任意兩兩個點之間的關系。
然後根據關系可以得出來一個一元多項式的矩陣。
然後就用高斯消元求出矩陣即可。
#include
#include
#include
#include
#include
#include
using namespace std;
#define eps 1e-6
#define zero(x) ((fabs(x)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;jque;
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
