期望

#include<bits/stdc++.h>
using namespace std;
#define M 100004
struct node{
int nxt,to;double dis;
}e[M*2];
int hd[M],cnt,dian[M],ru[M];
void add(int u,int v,double w){
    e[++cnt].nxt=hd[u];
    e[cnt].to=v;
    e[cnt].dis=w;
    hd[u]=cnt;
}
queue<int> q;
double dp[M];
int main(){
int n,m,u,v;
double w;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;++i){
        scanf("%d%d%lf",&u,&v,&w);
        add(v,u,w);
        dian[u]++;
        ru[u]++;
    }
    q.push(n);
    while(!q.empty()){
        int u=q.front();q.pop();
        for(int i=hd[u];i;i=e[i].nxt){
            int v=e[i].to;
            dp[v]+=(dp[u]+e[i].dis)/dian[v];
            ru[v]--;
            if(ru[v]==0) q.push(v);
        }
    }
    printf("%.2lf",dp[1]);
    return 0;
}

#include<bits/stdc++.h>
#define M 505
#define Q 250005
using namespace std;
int n,u[Q],v[Q],du[Q],m;
double a[M][M],b[M],x[M],ans[Q];
struct node{
	int nxt,to;
}e[Q];
int hd[Q],cnt;
void add(int u,int v){
	e[++cnt].nxt=hd[u];
	e[cnt].to=v;
	hd[u]=cnt;
}
void gaosi(int N){
	for(int i=1;i<=N;++i){
		int p=i;
		for(int j=i+1;j<=N;++j)
			if(fabs(a[j][i])>fabs(a[p][i])) p=j;
		if(i!=p)swap(a[i],a[p]);swap(b[i],b[p]);	
		for(int j=i+1;j<=N;++j){
			double k=a[j][i]/a[i][i];
			for(int qwe=i;qwe<=N;++qwe) a[j][qwe]-=k*a[i][qwe];
			b[j]-=k*b[i];
		}
	}
	for(int i=N;i>=1;--i){
		for(int j=i+1;j<=N;++j) b[i]-=x[j]*a[i][j];
		x[i]=b[i]/a[i][i];
	}
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;++i){
		scanf("%d%d",&u[i],&v[i]);
		add(u[i],v[i]);add(v[i],u[i]);
		du[u[i]]++;du[v[i]]++;
	}
	for(int i=1;i<n;++i){
		a[i][i]=1.0;
		for(int j=hd[i];j;j=e[j].nxt){
			int v=e[j].to;
			if(v!=n) a[i][v]=-1.0/du[v];
		}
	}
	b[1]=1.0;
	gaosi(n-1);
//	for(int i=1;i<=n;++i) printf("%.5lf\n",x[i]);
	for(int i=1;i<=m;++i){
		if(u[i]!=n) ans[i]+=x[u[i]]/du[u[i]];
		if(v[i]!=n) ans[i]+=x[v[i]]/du[v[i]];
	}
	sort(ans+1,ans+m+1);
	double sm=0;
	for(int i=1;i<=m;++i) sm+=ans[i]*(m-i+1);
	printf("%.3lf",sm);
	return 0;
}
//dp[i]=sigma(j(j!=n)):f_j/du_j
//dp[1]++