美团CODEM 初赛B 景区路线规划 概率DP

初赛B 景区路线规划 概率DP"/>

美团CODEM 初赛B 景区路线规划 概率DP

美团旅行团队最近打算推出一项新服务，为景区的各个景点规划游览路线，提升游客满意度。其中一个重要的问题是对于一个景区道路网，求出游客的满意度的期望值。基于用户的喜好差异，我们需要对男性游客和女性游客的满意度分别计算。
景区被描述成一张n个点、m条边的无向图（无重边，无自环）。每个点代表一个景点，第i个景点游览需要耗费ci分钟，会让男性游客和女性游客的满意度分别增加h1i和h2i（满意度初始值都为0）。每条边代表一条路，第i条边连接编号为xi,yi的两个景点，从景点xi走到yi和从yi走到xi的时间都是ti分钟。
每个游客在景区中最长可以游览k分钟，最开始会随机的通过不同大门进入到一个景点开始游览，每游览完一个项目，游客会等概率随机选择一个可以从当前景点直达且来得及游览的景点作为下一个游览目标（已经游览过的景点也会因为有各种新活动而让游客再次考虑，所以我们这里不区分景点是否已经游览过）。如果游览完一个景点后，周围没有来得及游览的景点，本次游玩就结束了。
请你分别计算小y和妹子在游玩结束后开心度的期望。
输入描述:

第一行给出三个空格隔开的整数，分别表示n, m, k(0 < n ≤ 100, 1 * 60 ≤ k ≤ 8 * 60)
接下来的n行，每行三个空格隔开的整数，分别表示ci, h1i, h2i (10 ≤ ci ≤ 60，0 < h1i, h2i ≤ 100)
接下来的m行，每行三个空格隔开的整数，分别表示xi, yi, ti (0 < ti ≤ 15)

输出描述:

两个用空格隔开的实数，分表表示小y和妹子开心度的期望，精确到小数点后5位。

输入例子1:

5 4 60
25 12 83
30 38 90
16 13 70
22 15 63
50 72 18
2 1 7
3 1 7
4 3 1
5 3 10

输出例子1:

39.20000 114.40000

解法：常规概率DP。pair

///美团CODEM 景区路线规划#include <bits/stdc++.h>
using namespace std;
const int maxn = 200;
#define MP make_pair
int n, m, kk, edgecnt, head[maxn], c[maxn], h1[maxn], h2[maxn];
//pair<double ,double> dp[i][j]，表示到达并玩完第i个项目，当前剩余时间j,两个人的期望
struct edge{int to,w,next;
}E[maxn*maxn];
void init(){edgecnt=0;memset(head,-1,sizeof(head));
}
void add(int u, int v, int w){E[edgecnt].to = v, E[edgecnt].w = w,E[edgecnt].next = head[u], head[u] = edgecnt++;
}
pair <double, double> dp[maxn][500];
bool vis[maxn][500];
pair <double, double> dfs(int u, int k){if(vis[u][k]) return dp[u][k];vis[u][k] = 1;pair <double, double> &ret = dp[u][k], now;ret = MP(h1[u], h2[u]);int cnt = 0;for(int i = head[u]; ~i; i=E[i].next){int to = E[i].to;if(k >= c[to]+E[i].w) cnt++;}for(int i = head[u]; ~i; i=E[i].next){int to = E[i].to;if(k >= c[to]+E[i].w){now = dfs(to, k-E[i].w-c[to]);ret.first += now.first*1.0/cnt;ret.second += now.second*1.0/cnt;}}return ret;
}
int main()
{while(~scanf("%d %d %d", &n,&m,&kk)){for(int i=1; i<=n; i++){scanf("%d %d %d", &c[i],&h1[i],&h2[i]);}init();for(int i=1; i<=m; i++){int x,y,t;scanf("%d %d %d",&x,&y,&t);add(x, y, t);add(y, x, t);}pair <double, double> ans = MP(0,0), now;for(int i=1; i<=n; i++){now = dfs(i, kk - c[i]);ans.first += now.first*1.0/n;ans.second += now.second*1.0/n;}printf("%.5f %.5f\n", ans.first, ans.second);}return 0;
}