Codeforces 553E Kyoya and Train

Description

给定 $N$ 个点, $M$ 条边的有向图.
每条边有花费: 通过第 $i$ 条边的时间有 $ P _ {i1} $ 的概率为 $1$, $P _ {i2}$ 的概率为 $2$…
如果总用时超过 $T$ 则会被罚钱 $X$ 元, 求从 $1$ 号点到 $n$ 号点的最小期望花费.
$ N \leq 50, M \leq 100, T \leq 100000 $

Solution

考虑暴力DP, 记状态 $ dp _ {i, t} $ 表示到达 $i$ 号点, 且经过的时间为 $t$ 的最小期望花费, 转移十分显然.
同时因为状态之间按照时间构成一个拓扑图, 所以转移不存在环.

可以记 $S _ {e, t}$ 表示边 $e$ 在时刻 $t$ 之后后继状态的最小期望花费.

则可以用下面这个式子计算 $dp _ {e, t}$:

$e$ 是 $i$ 的出边.

接下来考虑如何计算 $S(e,t)$, 利用定义:

这样变成卷积形式, 分治 $FFT$ 即可.

Code

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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;
const int oo = 0x3f3f3f3f;
const int maxn = 200000 + 10;
const double PI = acos(-1.0);
template <typename T> bool chkmax(T& a, T b) { return a < b ? a = b, 1 : 0; }
template <typename T> bool chkmin(T& a, T b) { return a > b ? a = b, 1 : 0; }
#define fst first
#define snd second
#define debug(x) cerr << #x << ":" << (x) << endl
#define REP(i, a, b) for(int i = (a), i##end = (b); i < i##end; ++i)
#define DREP(i, a, b) for(int i = (a)-1, i##bgn = (b); i >= i##bgn; --i)
template<typename T> T read() {
T n = 0, f = 1;
char ch = getchar();
for( ;!isdigit(ch); ch = getchar()) if(ch == '-') f = -1;
for( ; isdigit(ch); ch = getchar()) n = n * 10 + ch - 48;
return n * f;
}
struct Complex {
double real, imag;
Complex(double r = 0.0, double i = 0.0): real(r), imag(i) {}
Complex operator + (const Complex& rhs) const {
return Complex(real + rhs.real, imag + rhs.imag);
}
Complex operator - (const Complex& rhs) const {
return Complex(real - rhs.real, imag - rhs.imag);
}
Complex operator * (const Complex& rhs) const {
return Complex(real*rhs.real - imag*rhs.imag, real*rhs.imag + imag*rhs.real);
}
Complex operator / (const double& div) const {
return Complex(real / div, imag / div);
}
};
int rev[maxn];
void DFT(Complex *x, int N, int t) {
for(int i = 0; i < N; i++)
if(i < rev[i]) swap(x[i], x[rev[i]]);
for(int l = 2; l <= N; l <<= 1) {
Complex wn = Complex(cos(2*PI*t/l), sin(2*PI*t/l));
for(int i = 0; i < N; i += l) {
Complex w = Complex(1, 0);
for(int j = 0; j < (l >> 1); j++, w = w * wn) {
Complex L = x[i + j];
Complex R = x[i + j + (l >> 1)] * w;
x[i + j] = L + R;
x[i + j + (l >> 1)] = L - R;
}
}
}
if(!~t) for(int i = 0; i < N; i++) x[i] = x[i] / N;
}
const int N = 100 + 5;
int dis[N][N];
int n, m, t, x;
struct Edge {
int u, v, c;
double p[maxn];
void input() {
u = read<int>(), v = read<int>(), c = read<int>();
chkmin(dis[u][v], c);
for(int i = 1; i <= t; i++) p[i] = double(read<int>()) / 100000.0;
}
}E[N];
Complex A[maxn], B[maxn];
double S[N][maxn], f[N][maxn];
void calc(int l, int r, int mid) {
static int base, len;
for(int k = 0; k < m; k++) {
int v = E[k].v;
for(base = 1, len = 0; base <= 2*r-l-mid+1; base <<= 1) ++ len;
for(int i = 0; i < base; i++) rev[i] = (rev[i>>1] >> 1) | ((i&1) << (len-1));
for(int i = 0; i < base; i++) A[i] = B[i] = Complex(0, 0);
for(int i = 0; i < r-mid; i++) A[i] = Complex(f[v][r-i], 0);
for(int i = 1; i <= r-l; i++) B[i-1] = Complex(E[k].p[i], 0);
DFT(A, base, 1); DFT(B, base, 1);
for(int i = 0; i < base; i++) A[i] = A[i] * B[i];
DFT(A, base, -1);
for(int i = l; i <= mid; i++) S[k][i] += A[r-i-1].real;
}
}
void cdq_solve(int l, int r) {
if(l == r) {
for(int i = 0; i < m; i++)
chkmin(f[E[i].u][l], S[i][l] + E[i].c);
return;
}
int mid = (l + r) >> 1;
cdq_solve(mid+1, r);
calc(l, r, mid);
cdq_solve(l, mid);
}
int main() {
#ifndef ONLINE_JUDGE
freopen("data.txt", "r", stdin);
freopen("ans.txt", "w", stdout);
#endif
memset(dis, oo, sizeof dis);
n = read<int>(), m = read<int>(), t = read<int>(), x = read<int>();
for(int i = 1; i <= n; i++) dis[i][i] = 0;
for(int i = 0; i < m; i++) E[i].input();
for(int k = 1; k <= n; k++)
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++)
chkmin(dis[i][j], dis[i][k] + dis[k][j]);
for(int i = 1; i <= n; i++) {
for(int T = 0; T <= t; T++) f[i][T] = (i == n) ? 0 : oo;
for(int T = t+1; T <= 2*t; T++) f[i][T] = dis[i][n] + x;
}
calc(1, t*2, t);
cdq_solve(0, t);
printf("%.10lf\n", f[1][0]);
return 0;
}