题目大意 && 解 (转)

$zgjkt$

Code

#include <cstdio>
#include <cctype>
#include <queue>
#include <algorithm>
#define rep(i,x,y) for (int i=x; i<=y; ++i)
#define repd(i,x,y) for (int i=x; i>=y; --i)

using namespace std;
int n,m,u,v;
double f[100010],w,p;
struct edge
{
    int v;
    double w,p;
    bool operator < (const edge c) const
    {
        return w/p+f[v]<c.w/c.p+f[c.v];
    }
};
vector<edge> edg[100010];

inline int get()
{
    int ret;
    char ch;
    while (!isdigit(ch=getchar()));
    for (ret=ch-48; isdigit(ch=getchar()); ret=ret*10+ch-48);
    return ret;
}

int main()
{
    n=get(),m=get();
    rep(i,2,n)
        w=get(),edg[i-1].push_back((edge){i,w,1});
    rep(i,1,m)
    {
        u=get(),v=get(),scanf("%lf",&p),w=get();
        if (p>0)
            edg[u].push_back((edge){v,w,p});
    }
    repd(i,n-1,1)
    {
        sort(edg[i].begin(),edg[i].end());
        p=1;
        for (vector<edge>::iterator j=edg[i].begin(); j!=edg[i].end() && p>0; ++j)
            f[i]+=p*(j->w+j->p*f[j->v]),p*=1-j->p;
    }
    printf("%.2f\n",f[1]);
    return 0;
}