행복 경로

기대치가 가장 큰 dp, 유환 이동
강연통 분량 축소점을 생각한 후 블록 내 고스 소원 + 토폴로지 dp.
하지만 고스 소원은 맥스의 이동이 없었다.
그래서 링 최대치를 처리하는 방법:floyd
요약:
루프 이동을 처리하는 방법:
최단로(단원floyd)는 주로 max/min을 구한다.
고스 소원은 주로 기대를 구하는 것이다.
강연통분량의 축소점은 주로 문제 안에 뚜렷한 제시가 있거나 강연통분량 내부에 특수한 성질이 있다는 것이다.

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>

#define ll long long
#define inf 1e9
#define eps 1e-10
#define md
#define N 110
using namespace std;
double w[N],f[N][N],g[N][N];
int a[N][N];
int main()
{
	int n,m,S;
	double p; 
	scanf("%d%d",&n,&m);
	for (int i=1;i<=n;i++) scanf("%lf",&w[i]);
	scanf("%d%lf",&S,&p);
	n++;
	for (int i=1;i<=n;i++)
	  for (int j=1;j<=n;j++)
	    g[i][j]=-inf;
	for (int i=1;i<=m;i++)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		a[x][y]=1; g[x][y]=w[y]*p;
	}
	w[n]=0;
	for (int i=1;i<=n;i++) g[i][n]=0;
	for (int t=1;t<=50;t++,p*=p)
	{
		for (int i=1;i<=n;i++)
		  for (int j=1;j<=n;j++)
		    f[i][j]=-inf;
		for (int k=1;k<=n;k++)
		  for (int i=1;i<=n;i++)
		    for (int j=1;j<=n;j++)
		      f[i][j]=max(f[i][j],g[i][k]+g[k][j]*p);
		memcpy(g,f,sizeof(f));
		//printf("%.2lf : %.2lf %.2lf %.2lf
",p,g[1][2],g[1][3],g[1][4]);
	}
	double ans=-inf;
	for (int i=1;i<=n;i++)
	    ans=max(ans,f[S][i]);
	printf("%.1lf
",ans+w[S]);
	return 0;
}