学好数理化，走遍天下都不怕

DTOJ2603 不稳定的传送门

发表于 更新于 分类于

题目

题目描述

C国里一共有$N$个城镇，编号为$1$到$N$
其中第$i$个城镇与第$i+1$个城镇连接着一条收费为$c_i$的从$i$到$i+1$的单向道路$(1\leqslant i<n)$
现在，杰杰作为一个旅行者，他的任务就是从第$1$个城镇出发，到达编号为$N$的城镇
他觉得这样会很无聊，海克斯科技公司也是这么认为的，所以该公司在若干个城镇里设置了共$M$个单向传送门
每个传送门有$4$个参数$s,t,p,w$
$s$表示传送门的出发城镇，$t$表示传送门的传送目标城镇，保证$t$大于$s$，$w$表示使用该传送门的花费，$p$为传送成功的概率，若传送失败会自动返回出发的城市而且该传送门会永久损坏；而且无论传送成功与否，只要使用了该传送门就得花费$w$
现在，杰杰正在规划他的旅行方案。请你帮他规划一条最优策略，使得旅途期望花费最小

输入格式

第一行有两个整数$N$和$M$
第二行有$N-1$个用空格隔开的整数，第$i$个数为$c_i$，意义如上述所示
接下来有$M$行，每行有$4$个数$s,t,p,w$，表示一个传送门的属性，意义如上述所示，其中$s,t,w$为整数

输出格式

一个数，表示期望最小花费，小数点后四舍五入保留两位小数

样例

样例输入

1
2
3
4
4 2
30 30 30
1 4 0.5 30
2 3 0.9 10

样例输出

1
66.50

数据范围与提示

对于$30\%$的数据，每个城镇出发的传送门不超过$5$, 且$n\leqslant 1000$
对于$100\%$的数据，$1\leqslant n\leqslant 10^5,1\leqslant m\leqslant 10^5, 1\leqslant w\leqslant 100, 0\leqslant p\leqslant 1, 1\leqslant ci\leqslant 100$

题解

从题目中，我们可以看出这是个概率DP，并且是单向行走的
因此我们从$N$向$1$进行DP
我们可以建一个图，对于每一条边，存储$p$（概率）和$w$（花费）（对于从$i$到$i+1$的边，概率就是$1$）
分别写出对于同一个点的任意两条边$x$和$y$不同选择顺序的式子，化简后可以得到得：如果$dp[x.to]+\frac{x.w}{x.p}\leqslant dp[y.to]+\frac{y.w}{y.p}$，那么x比y更优，所以优先选择$x$
但是在计算$x$时，要用到$y$的结果，所以虽然优先选择$x$，但是在计算顺序上$y$在$x$之前
附上代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
//自己写的太难看了，贴的是同学的代码
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <string>
#include <cstring>
#include <vector>
using namespace std;
int N,M;
struct node {int x;double p,val;};
vector<node> ed[100005];
double dp[100005];

bool cmp(node x,node y)
{
    return dp[x.x]+x.val/x.p>dp[y.x]+y.val/y.p;
}
int main()
{
    freopen("portal.in","r",stdin);
    freopen("portal.out","w",stdout);
    scanf("%d %d",&N,&M);
    
    double a;
    node x;
    for (int i=1;i<=N-1;i++)
    {
        scanf("%lf",&a);
        x.x=i+1;
        x.p=1;
        x.val=a;
        ed[i].push_back(x);
    }
    int st;
    for (int i=1;i<=M;i++)
    {
        scanf("%d %d %lf %lf",&st,&x.x,&x.p,&x.val);
        ed[st].push_back(x);
    }
    for (int i=1;i<=N;i++) dp[i]=999999999;
    dp[N]=0;
    for (int i=N-1;i>=1;i--)
    {
        sort(ed[i].begin(),ed[i].end(),cmp);
        for (int j=0;j<ed[i].size();j++)
        {
            x=ed[i][j];
            dp[i]=min(dp[i],
                       dp[i]*(1-x.p)+dp[x.x]*x.p+x.val);
        }
    }
    printf("%.2lf\n",dp[1]);
    return 0;
}