题目

P4316 绿豆蛙的归宿

#include<bits/stdc++.h>
using namespace std;
const int N=110000;
struct edge
{
	int to,nxt,co;
}e[N*2];
int h[N],E=0;
int n,m;
int deg[N],use[N],ged[N];
double f[N],g[N];
void addedge(int u,int v,int w)
{
	deg[u]++;
	use[v]++;
	E++;
	e[E].to=v,e[E].nxt=h[u],e[E].co=w;
	h[u]=E;
	return;
}
void topsort1()
{
	queue<int> q;
	q.push(1);
	g[1]=1;
	for(int i=1;i<=n;i++) ged[i]=use[i];
	while(!q.empty())
	{
		int u=q.front();
		q.pop();
		for(int i=h[u];i;i=e[i].nxt)
		{
			int v=e[i].to;
			g[v]+=g[u]/deg[u];
			use[v]--;
			if(!use[v]) q.push(v);
		}
	}
	for(int i=1;i<=n;i++) use[i]=ged[i];
	return;
}
void topsort()
{
	queue<int> q;
	q.push(1);
	while(!q.empty())
	{
		int u=q.front();
		q.pop();
		for(int i=h[u];i;i=e[i].nxt)
		{
			int v=e[i].to;
			int w=e[i].co;
			f[v]+=(f[u]+w*g[u])/deg[u];
			use[v]--;
			if(!use[v]) q.push(v);
		}
	}
	return;
}
int main()
{
	scanf("%d%d",&n,&m);
	int u,v,w;
	for(int i=1;i<=m;i++)
	{
		scanf("%d%d%d",&u,&v,&w);
		addedge(u,v,w);
	}
	topsort1();
	topsort();
	printf("%.2lf\n",f[n]);
	return 0;
}