题意：
DAG网络中，求从节点1走到节点n的期望的代价，具体代价的定义见题目即可。
思路：
这类概率dp的递推比较经典，很好写出递推式
用两次期望递推，第一次dp1[i]求 i点到N点的期望时间，第二次dp2[i]求i到N的期望代价，图是个拓扑图，所以我们可以从后往前推（求DFS求拓扑序就是逆序）
下面借用一下别人的式子。
比赛中没有时间写这个题了，水题花了太多时间，Orz
赛后补的时候，用了一个vis数组，在求dp数组的时候，脑子抽了，搞了一个！vis才能访问，于是一直WA，因为这个是图结构，不是树结构，这次用的节点下次还会用，因为这个特点，还需加一下记忆化即可。。。Orz,应该来说是个不算难的题。
代码：
#include<bits/stdc++.h> using namespace std; const int N=1e5+10; vector<int>G[N]; int n,m; //因为dp转移时拓扑序的，所以拓扑排序时必要的 double dp1[N];//dp1[i]表示i点到达n点的期望天数 double dp2[N];//表示i点到达n点的花费 int vis[N]; void init(int n){ for(int i=0;i<=n;i++) G[i].clear(); for(int i=1;i<=n;i++){ dp1[i]=dp2[i]=0; } } double toposort(int u){ if(u==n)return 0; if(dp1[u])return dp1[u]; double ans=0; for(int i=0;i<G[u].size();i++){ int v=G[u][i]; ans+=toposort(v); } return dp1[u]=(ans+G[u].size()+1)/G[u].size(); } double toposort2(int u){ if(u==n)return 0; if(dp2[u])return dp2[u]; double ans=0; for(int i=0;i<G[u].size();i++){ int v=G[u][i]; ans+=toposort2(v); } return dp2[u]=(ans+dp1[u]*(G[u].size()+1))/G[u].size(); } //在题目中无用，拓扑排序的代码 bool dfs(int u){ vis[u]=-1; for(int i=0;i<G[u].size();i++){ int v=G[u][i]; if(vis[v]<0)return false; else if(!vis[v]&&dfs(v)==false)return false; } vis[u]=1; //这里可以保存排序topo[t--]=u;插入到拓扑序的首部 return true; } int main() { int T; scanf("%d",&T); while(T--){ scanf("%d%d",&n,&m); init(n); for(int i=0;i<m;i++){ int u,v; scanf("%d%d",&u,&v); G[u].push_back(v); } toposort(1); printf("%.2f ",toposort2(1)); } return 0; }