bzoj 2306

 1 #include<bits/stdc++.h>
 2 #define INF 0x7fffffff
 3 #define LL long long
 4 #define N 100005
 5 using namespace std;
 6 inline int ra()
 7 {
 8     int x=0,f=1; char ch=getchar();
 9     while (ch<‘0‘ || ch>‘9‘) {if (ch==‘-‘) f=-1; ch=getchar();}
10     while (ch>=‘0‘ && ch<=‘9‘) {x=x*10+ch-‘0‘; ch=getchar();}
11     return x*f;
12 }
13 double p,ans,a[101],f[101][101],g[101][101];
14 int main()
15 {
16     int n=ra(),m=ra();
17     for (int i=1; i<=n; i++)
18         scanf("%lf",&a[i]);
19     int st=ra(); 
20     scanf("%lf",&p);
21     memset(f,0xc2,sizeof(f));
22     for (int i=1; i<=n; i++)
23         f[i][i]=0;
24     for (int i=1; i<=m; i++)
25     {
26         int x=ra(),y=ra();
27         f[x][y]=a[y];
28     }
29     double tmp=p;
30     for (int T=0; T<=70; T++,tmp*=tmp)
31     { 
32         memset(g,0xc2,sizeof(g));
33         for (int k=1; k<=n; k++)
34             for (int i=1; i<=n; i++)
35                 for (int j=1; j<=n; j++)
36                     g[i][j]=max(g[i][j],f[i][k]+f[k][j]*tmp);
37         memcpy(f,g,sizeof(f));
38     }
39     for (int i=1; i<=n; i++)
40         ans=max(ans,f[st][i]);
41     printf("%.1lf\n",ans*p+a[st]);
42     return 0;
43 }