【期望+状压DP】 2021 CCPC G

红太狼 2024-03-01 07:47 28阅读 0赞

[Problem - G - Codeforces][]

题意：

![dca96a9702b54c1590f9e441a4f72d6e.png][]

![5d06c9b74c66405c894289d08cb22684.png][]

![d36ebf962e874913b1546a335ac08e32.png][]

思路：

注意到 k 的范围是18，可以考虑状压

要求最小的期望长度，我们可以遍历所有可能的路径，统计这些路径的期望长度的最小值即可

那么怎么遍历呢？这里很经典的处理方式是状压DP

设 dp\[x\]\[st\] 为 当前处于 x 结点上，且经过的结点状态为 st 的最小期望路径长度

这里的状压DP我们用记忆化搜索解决

可能关于期望的状压DP用记忆化搜索会好处理一点（？）

注意到在转移过程中需要用到用了哪辆车的两点之间的最短路，因此我们考虑预处理这个最短路，这个就类似于分层图的思想搞一搞就好了

Code：

#include <bits/stdc++.h>
    
    #define int long long
    
    constexpr int N = 1e5 + 10;
    constexpr int Inf = 1e18;
    
    struct ty2 {
    	int x, dis;
    	bool operator < (const ty2 & a) const {
    		return a.dis < dis;
    	}
    };
    
    std::vector<std::pair<int,int> > adj[N];
    std::priority_queue<ty2> q;
    
    int n, m, k;
    int a[N];
    int dis[20][N], vis[N];
    double t, r;
    double dp[20][(1 << 20)], p[N];
    
    void dij(int st, int id) {
    	for (int i = 1; i <= n; i ++) {
    		vis[i] = 0;
    		dis[id][i] = Inf;
    	}
    	dis[id][st] = 0;
    	q.push({st, dis[id][st]});
    	while(!q.empty()) {
    		auto u = q.top();
    		q.pop();
    		if (vis[u.x]) continue;
    		vis[u.x] = 1;
    		for (auto [v, w] : adj[u.x]) {
    			if (dis[id][v] > dis[id][u.x] + w) {
    				dis[id][v] = dis[id][u.x] + w;
    				q.push({v, dis[id][v]});
    			}
    		}
    	}
    }
    double dfs(int x, int st) {
    	if (dp[x][st]) return dp[x][st];
    	double res = 1.0 * p[x] * dis[x][n] / t + (1.0 - p[x]) * dis[x][n] / r;
    	for (int j = 1; j <= k; j ++) {
    		if ((st >> (j - 1)) & 1) continue;
    		res = std::min(res, 1.0 * (1 - p[x]) * dis[x][n] / r + p[x] * (1.0 * dis[x][a[j]] / t + dfs(j, st | (1 << (j - 1)))));
    	}
    	return dp[x][st] = res;
    }
    void solve() {
    	std::cin >> t >> r >> n >> m;
    	for (int i = 1; i <= m; i ++) {
    		int u, v, w;
    		std::cin >> u >> v >> w;
    		adj[u].push_back({v, w});
    		adj[v].push_back({u, w});
    	}
    
    	std::cin >> k;
    	for (int i = 1; i <= k; i ++) {
    		std::cin >> a[i] >> p[i];
    		p[i] /= 100.0;
    	}
    
    	a[0] = 1, p[0] = 1.0;
    	for (int i = 0; i <= k; i ++) {
    		dij(a[i], i);
    	}
    
    	if (dis[0][n] >= Inf) {
    		std::cout << -1 << "\n";
    		return;
    	}
    	std::cout << std::fixed << std::setprecision(10) << dfs(0, 0) << "\n";
    }
    signed main() {
    	std::ios::sync_with_stdio(false);
    	std::cin.tie(nullptr);
    
    	int t = 1;
    	while(t --) {
    		solve();
    	}
    	return 0;
    }

[Problem - G - Codeforces]: https://codeforces.com/gym/103447/problem/G
[dca96a9702b54c1590f9e441a4f72d6e.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/01/66071b044c474d068de694ef52d1c99b.png
[5d06c9b74c66405c894289d08cb22684.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/01/b400bf6faf604e4f927eafba9f1c1b32.png
[d36ebf962e874913b1546a335ac08e32.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/01/cf3ef0d49e2b4e738cf863ef0cfe2067.png