题面戳我

Solution

• 反向建图跑拓扑排序，顺便处理\(dp\)
• 假设某条边是\(u \rightarrow v (dis)\) ，那么转移方程就是\(dp[v]+=(dp[u]+dis)/in[v]\)
• 根据题意我们可以知道，每个点选择道路的概率是一样的，所以只能这么做。（重点在看什么的概率相同（雾大概是这样）

Code

//It is coded by ning_mew on 7.22

#include<bits/stdc++.h>

using namespace std;

const int maxn=1e5+7;

int n,m;

int head[maxn],cnt=0;

struct Edge{int nxt,to,dis;}edge[maxn*2];

int in[maxn],inin[maxn],out[maxn];

double dp[maxn];

void add(int from,int to,int dis){

	edge[++cnt].nxt=head[from];edge[cnt].to=to;

	edge[cnt].dis=dis;head[from]=cnt;

}

int main(){

	scanf("%d%d",&n,&m);

	for(int i=1;i<=m;i++){

		int a,b,c;scanf("%d%d%d",&a,&b,&c);

		add(b,a,c);in[a]++;inin[a]++;out[b]++;

	}

	queue<int>Q;while(!Q.empty())Q.pop();

	Q.push(n);dp[n]=0;

	while(!Q.empty()){

		int u=Q.front();Q.pop();

		for(int i=head[u];i!=0;i=edge[i].nxt){

			int v=edge[i].to;

			dp[v]+=(dp[u]+1.0*edge[i].dis)/inin[v];

			in[v]--;if(!in[v])Q.push(v);

		}

	}printf("%0.2lf\n",dp[1]); return 0;

}

博主蒟蒻，随意转载。但必须附上原文链接：http://www.cnblogs.com/Ning-Mew/，否则你会场场比赛爆0！！！