题目大意

一共有$n$个城镇，第$i$个城镇到第$i+1$个城镇有一条收费$c_i$的单向道路

除此之外，再给出$m$个单向传送门，可以从传送门规定的起始地去往目的地，同样需要收费$w_j$

但它传送成功的概率只有$p_j$，失败会传送回起始地，并且无论成败，使用了传送门就需要花费$w_j$

现在若要从第$1$个城镇前往第$n$个城镇，询问最小期望花费

数据范围

$1\leqslant n,m\leqslant 10^5\ ,\ 1\leqslant c_i,w_j\leqslant 100\ ,\ 0\leqslant p_j\leqslant 1$

题解

听说这道题是概率dp，具体怎么做？

为了方便解题，在预处理的时候，要把单向道路转为传送成功的概率为$1$的单向传送门，

若$f[i]$表示从第$i$个城镇走到第$n$个城镇的最小期望花费

则转移到第$i$个城镇时，需要枚举每条从第$i$个城镇出发的道路，并以最优顺序存储$(i,v_1,p_1,w_1),(i,v_2,p_2,w_2),(i,v_3,p_3,w_3)...$

于是状态转移方程就是$f[i]=p_1f[v_1]+w_1+(1-p_1)(p_2f[v_2]+w_2+(1-p_2)(p_3f[v_3]+w_3+(1-p_3)(...)))$，这道题就解决啦！

等等，最优顺序是什么？

先把状态转移方程化简，令$r_i=p_if[v_i]+w_i\ ,\ q_i=1-p_i$

则状态转移方程为$f[i]=r_1+q_1(r_2+q_2(r_3+q_3(...)))=r_1+q_1r_2+q_1q_2r_3+(...)$

此时如果把第一条路$(r_1,q_1)$和第二条路$(r_2,q_2)$的顺序调换，能使得状态转移更优

那么需要满足$r_2+q_2r_1+q_2q_1r_3+(...) < r_1+q_1r_2+q_1q_2r_3+(...)$

由于省略部分$(...)$类似$(q_2q_1r_3,q_1q_2r_3)$是相同的，那么能够只需要满足$r_2+q_2r_1 < r_1+q_1r_2$即可

将$q_i=1-p_i$代回去，得到$r_2p_1 < r_1p_2$

即只要满足$ \frac{r_1}{p_1} > \frac{r_2}{p_2}$，就把这两条道路交换顺序，每两条顺序相邻的道路用相邻交换法排序

要注意的是，如果$p_i=0$，那么无需把这条边加入统计范围...

程序

#include<cstdio>
#include<cstring>
#include<cmath>
#include<cctype>
#include<algorithm>
#define maxn 100050
#define For(i,l,r) for(int i=l;i<=r;i++)
#define Ford(i,r,l) for(int i=r;i>=l;i--)
#define goedge(i,x) for(int i=last[x];i;i=e[i].next)
using namespace std;
inline int read(){
    int x=0,f=1;char ch=getchar();
    while (!isdigit(ch)) {if (ch=='-') f=-1;ch=getchar();}
    while (isdigit(ch)) {x=x*10+ch-48;ch=getchar();}
    return x*f;
}

int n,m,et,top;
double dp[100500];
struct edge{int s,t,w,next;double p;}e[200500];
int last[100500],cur[100500];
inline void addedge(int s,int t,double p,int w){
    e[++et]=(edge){s,t,w,last[s],p};last[s]=et;
}
inline int cmp(int x,int y){
    return dp[e[x].t]+e[x].w/e[x].p < dp[e[y].t]+e[y].w/e[y].p;
}

int main(){
    n=read(),m=read();
    For(i,1,n-1) addedge(i,i+1,1,read());
    For(i,1,m){
        int s=read(),t=read();
        double p;scanf("%lf",&p);
        int w=read();
        if (p==0) continue;
        addedge(s,t,p,w);
    }
    Ford(x,n-1,1){
        top=0;
        goedge(i,x) cur[++top]=i;
        sort(cur+1,cur+top+1,cmp);
        dp[x]=(double)e[cur[top]].p*dp[e[cur[top]].t]+e[cur[top]].w;
        Ford(i,top-1,1)
            dp[x]=(double)e[cur[i]].p*dp[e[cur[i]].t]+e[cur[i]].w+(1-e[cur[i]].p)*dp[x];
    }
    printf("%.2lf\n",dp[1]);
    return 0;
}