第一个 完全自己想的期望+完全自己做的T3 并且 +1遍AC
Description：
Solution：
一看是一道期望题。
再一看，发现，v<=300,n,m<=2000有点意思。
大概复杂度n^2确定。
有一张图？任意两点间最短路？300就是floyd的提示嘛！！
预处理floyd确定。
发现，阶段比较明显，第i个阶段
一看就是一道期望dp题了。
dp状态：显然要记录第i阶段，显然要知道用了几个申请。恰好n方开的下。
可以设dp[i][j]，表示前i阶段，包括这个阶段用了j个申请，期望值的最小值。
但是，不知道可能会在哪里，根本无法转移。
为了记录在哪里，
如果设dp[i][j][0/1/2]表示，前i阶段，用了j个申请，这一次未申请、申请失败、申请成功的期望。
这是个什么玩意啊，根本就是错的。
因为，dp是一种决策或者说选择。我们只能选择申请或者不申请，并不能选择通过不通过。
而且，最后我们要求的是，进行最后一次申请后的期望。那么，最后怎么合并呢？取min还是？
完全就挂了~~
所以，为了知道选择，还要知道位置，那么
就设dp[i][j][0/1]表示，前i阶段，包括这个阶段用了j个申请，这一次有没有用申请。（仅有没有，过不过不知道。）
这样就可以转移了。
因为，知道了在哪里。而且可以决策。
如果上一次没有用，就在c[i-1]，否则一定概率在d[i-1]一定概率在 c[i-1]
转移的时候，当前是0，1同理处理一下概率即可。
dp转移的正确性其实是：
E(Y)=E(X+e)=E(X)+E(e)=E(X)+p1*dis1+p2*dis2+p3*dis3+p4*dis4注意，本质上，dp的转移思想还是，从上一个状态选择一个方案，算出这个转移的代价，取最小的转移过来。
所以，min肯定是在外面的。
至于期望的转移是否正确，就审查一下是否所有的情况概率和是1就好啦~！
Code：
#includeusing namespace std;const int N=2000+3;const int M=300+3;const int inf=0x3f3f3f3f;const double big=1000000007.00;int dis[M][M];int c[N],d[N];double f[N][N][2];double p[N];int n,m,v,e;int main(){ scanf("%d%d%d%d",&n,&m,&v,&e); for(int i=1;i<=n;i++) scanf("%d",&c[i]); for(int i=1;i<=n;i++) scanf("%d",&d[i]); for(int i=1;i<=n;i++) scanf("%lf",&p[i]); int x,y,z; memset(dis,inf,sizeof dis); for(int i=1;i<=e;i++){ scanf("%d%d%d",&x,&y,&z); if(x==y) continue; dis[x][y]=min(dis[x][y],z); dis[y][x]=dis[x][y]; } for(int k=1;k<=v;k++){ dis[k][k]=0; for(int i=1;i<=v;i++) for(int j=1;j<=v;j++){ dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]); } } for(int i=1;i<=n;i++){ for(int j=0;j<=m;j++) f[i][j][0]=f[i][j][1]=big; } f[1][0][0]=0.0; f[1][1][1]=0.0; for(int i=2;i<=n;i++){ for(int j=0;j<=min(i,m);j++){ f[i][j][0]=min(f[i-1][j][0]+dis[c[i-1]][c[i]], f[i-1][j][1]+p[i-1]*dis[d[i-1]][c[i]]+(1.00-p[i-1])*dis[c[i-1]][c[i]]); if(j>=1) f[i][j][1]=min( (1.00-p[i])*(f[i-1][j-1][0]+dis[c[i-1]][c[i]])+ p[i]*(f[i-1][j-1][0]+dis[c[i-1]][d[i]]), (1.00-p[i])*(f[i-1][j-1][1]+p[i-1]*dis[d[i-1]][c[i]]+(1.00-p[i-1])*dis[c[i-1]][c[i]])+ p[i]*(f[i-1][j-1][1]+p[i-1]*dis[d[i-1]][d[i]]+(1.00-p[i-1])*dis[c[i-1]][d[i]]) ); } } double ans=big; for(int j=0;j<=m;j++){ ans=min(ans,min(f[n][j][0],f[n][j][1])); } printf("%.2lf",ans); return 0;}