首页 > 其他 > 详细

bzoj 2306

时间:2017-02-06 19:45:23      阅读:218      评论:0      收藏:0      [点我收藏+]

%%%%http://blog.csdn.net/popoqqq/article/details/43926365

 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 }

 

bzoj 2306

原文:http://www.cnblogs.com/ccd2333/p/6371276.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!