题目大意
给定 $n$ 个点 $m$ 条边的带权（长度）无向图，图中有 $k$ 个点，其中第 $i$ 个点有一辆自行车，有 $p_i$ 的概率损坏，只有到达该点才知道自行车是否损坏。
已知 Bessie 的步行速度为 $t$，骑车速度为 $r$，现在她从 $1$ 号点出发，求出一种路径方案，使得期望时间最短。
$1\le n,m\le 10^5$，$k\le 18$。
题解
首先不难发现，除节点 $1$、节点 $n$ 和其他 $k$ 个节点之外都是无用的，可以做 $k + 1$ 遍最短路求出这些点之间的距离的距离。
注意到 $k$ 很小，套路考虑状压 DP，$S$ 表示当前经过的自行车点的集合，则每次转移需要从集合中的一个点到集合外的点，可以设 $f(S, i)$ 表示当前集合为 $S$，在节点 $i$ 的从 $1$ 到 $i$ 的最小期望长度，其中要考虑要么全部损坏，或是其中一次拿到自行车并直接走到 $n$。则有转移
$$
f(S\cup\{j\}, j)=\min_{i\in S\land j\not\in S}\left\{f(S, i)+\prod_{k\in S} p_k\left(\frac{\delta(i,j)}t+\frac{(1-p_j)\delta(j,n)}{r}\right)\right\}
$$
其中，初值为 $f(\{i\},i)=\dfrac{\delta(1,i)}t+\dfrac{(1-p_i)\delta(i,n)}r$。
答案即为 $\min\limits_{i\in S}\left\{f(S, i)+\prod\limits_{j\in S}p_j\dfrac{\delta(i, n)}t\right\}$。
时间复杂度 $O(kn\log m+2^kk^2)$，可以用 $\text{lowbit}$ 优化常数。
代码
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
| int n, m, tt, rr, kk;
cin >> tt >> rr >> n >> m;
vector<vector<pair<int, int>>> e(n + 1);
for (int u, v, w; m--;) {
cin >> u >> v >> w;
e[u].emplace_back(v, w);
e[v].emplace_back(u, w);
}
auto Dijkstra = [&](int s) {
vector<bool> vis(n + 1);
vector<int> dis(n + 1, INT32_MAX / 2);
dis[s] = 0;
priority_queue<pair<int, int>> q;
q.push({0, s});
while (q.size()) {
int u = q.top().second; q.pop();
if (vis[u]) continue;
vis[u] = true;
for (auto &[v, w] : e[u])
if (dis[v] > dis[u] + w) {
dis[v] = dis[u] + w;
q.push({-dis[v], v});
}
}
return dis;
};
cin >> kk;
vector<pair<int, int>> cycle(kk);
for (auto &c : cycle) cin >> c.first >> c.second;
vector<vector<int>> dis(kk);
dis[0] = Dijkstra(1);
if (dis[0][n] == INT32_MAX / 2) return cout << "-1\n", 0;
double ans = dis[0][n] * 1.0 / tt;
vector<vector<double>> f(1 << kk, vector<double>(kk, 1e18));
for (int i = 0; i < kk; ++i) dis[i] = Dijkstra(cycle[i].first);
for (int i = 0; i < kk; ++i)
f[1 << i][i] = 1.0 * dis[i][1] / tt + 0.01 * (100 - cycle[i].second) * dis[i][n] / rr;
for (int i = 1; i < (1 << kk); ++i) {
double cur = 1;
for (int j = 0; j < kk; ++j)
if (i >> j & 1) cur *= cycle[j].second * 0.01;
for (int j = 0; j < kk; ++j)
for (int k = 0; (i >> j & 1) && k < kk; ++k)
if (~i >> k & 1)
f[i | (1 << k)][k] = min(f[i | (1 << k)][k], f[i][j] + cur * (1.0 * dis[j][cycle[k].first] / tt + 0.01 * dis[k][n] * (100 - cycle[k].second) / rr));
}
for (int i = 1; i < (1 << kk); ++i) {
double cur = 1;
for (int j = 0; j < kk; ++j)
if (i >> j & 1) cur *= cycle[j].second * 0.01;
for (int j = 0; j < kk; ++j) {
if (i >> j & 1) ans = min(ans, f[i][j] + cur * dis[j][n] / tt);
}
}
printf("%.7lf", ans);
return 0;
}
|