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]步到达终点。这种状态的转移是刷表法
还可以拓扑排序，直接很数学地倒着算一遍。（待完成
// 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;
}