https://www.luogu.com.cn/problem/P4316

本题暂时只写了用期望dp经典套路，套上期望DP的基本套路，设dp(u)为到达u点的期望长度。

期望dp，也叫概率dp
一般来说，期望dp找到正确的状态后，转移是比较容易想到的。
但一般情况下，状态一定是“可数”的
事实上，将问题直接作为dp的状态是最好的。

如，问**“n人做XX事的期望次数”，那么不妨设计状态为f[i]表示i个人做完事的期望**。

转移一般是递推，通常分两种，一种是从上一个状态转移得（填表法），另一种是转移向下一个状态（刷表法）。

有时期望dp需以最终状态为初始状态转移，即逆推。

如f[i]表示期望还要走f[i]步到达终点。这种状态的转移是刷表法

还可以拓扑排序，直接很数学地倒着算一遍。（待完成

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

// Problem: 绿豆蛙的归宿
// Contest: AcWing
// URL: https://www.acwing.com/problem/content/219/
// Memory Limit: 64 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
using namespace std;
#define ll long long
//# define int long long
#define ull unsigned long long
#define pii pair<int,int>
#define double long double
#define baoliu(x, y) cout << fixed << setprecision(y) << x
#define endl  "\n"

const int N = 2e5 + 10;
const int M = 1e6 + 10;
const int inf = 0x3f3f3f3f;
const int mod = 998244353;
const double eps = 1e-8;
int n, m;
double dp[N];
struct node{
	int v,w;
};
	vector<node> e[N];
double dfs(int u){
	auto& res=dp[u];
	if(res>=0)return res;
	if(u==n)return res==0;
	res=0;
	int num=e[u].size();
	double p=1/(double)num;
		for(auto x:e[u]){
		int v=x.v,w=x.w;
		res+=p*(w+dfs(v));
	}
	return res;
}
void solve(){
	cin>>n>>m;
	memset(dp,-1,sizeof dp);
	for(int i=1;i<=m;i++){
	int u,v,w;cin>>u>>v>>w;
	e[u].push_back({v,w});
	}
	double ans=dfs(1);
	//其实是倒着做的，dfs（u）和dp【u]表示到从u到n的期望路径，其实可以从终点出发然后就不用记忆化搜索了
	//记忆化搜索也不难写，而且记忆化搜索是让递归回溯去计算答案的，不用人思考怎么走
	baoliu(ans,2);
}
int main() {
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(false);

    int t;
   t=1;
    while (t--) {
solve();
    }
    return 0;
}