Luogu

BZOJ

分析

设 $f[t][i][j]$ 表示走 $2^t$ 条边从 $i$ 到 $j$ 的最大值。这里暂时先不考虑起点的点权。

显然有 $f[t][i][j]=\max\big\{f[t-1][i][k]+p^t\times f[t-1][k][j]\big\}$ 。

当 $t$ 比较大的时候， $p^t$ 趋近于 $0$ ，可以直接忽略。于是只要算 $t\leq 50$ 就行了。

边界是 $f[1][u][v]=p*w[v]$ ，答案是 $\max\big\{w[s]+f[50][s][i]\big\}$ 。

注意边界的处理。细节见代码。

代码

// =================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// =================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;

const int N=100+10;

int n,m,s; double p;
double w[N],f[60][N][N];

int main() {
    scanf("%d%d",&n,&m);
    for (re int i=1;i<=n;++i) scanf("%lf",w+i);
    scanf("%d%lf",&s,&p);
    
    memset(f,-0x3f,sizeof(f));
    for (re int t=1;t<=50;++t)
        for (re int i=1;i<=n;++i)
            f[t][i][i]=0;
    for (re int i=1;i<=m;++i) {
        int u,v; scanf("%d%d",&u,&v);
        f[1][u][v]=p*w[v];
    }
    
    for (re int t=2;t<=50;++t,p*=p) {
        for (re int k=1;k<=n;++k)
            for (re int i=1;i<=n;++i)
                for (re int j=1;j<=n;++j)
                    f[t][i][j]=max(f[t][i][j],f[t-1][i][k]+p*f[t-1][k][j]);
    }
    
    double ans=0;
    for (re int i=1;i<=n;++i) ans=max(ans,w[s]+f[50][s][i]);
    printf("%.1lf\n",ans);
    return 0;
}