Description：

给一个联通无向图，每次随机选一条边联通，其他都不连通，如果面前有一条边联通，可以选择走也可以选择不走。问最优决策下期望多少次从 $1$ 走到 $n$ 。

$1\leqslant n\leqslant 10^5$

Solution：

首先一个位置的期望的计算方式为： $$ d[x]=\frac{\begin{align}\sum_{x\to y}\min(d[x],d[y])\end{align}}{deg[k]}+\frac m{deg[k]} $$ 那么我们如果知道了所有 $d[y]$ 的值，我们就可以二分 $d[x]$ ，因为推一下会发现满足单调性，然后用一个经典思路 $dijkstra$ 优化转移就行了，即每次拿出来一个最小的更新其他的。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<queue>

#include<cctype>

#include<cstring>

using namespace std;

int n,m;

#define MAXN 100010

struct edge

{

	int to,nxt;

}e[MAXN << 1];

int edgenum = 0;

int lin[MAXN] = {0};

int deg[MAXN];

void add(int a,int b)

{

	++deg[a];++deg[b];

	e[++edgenum] = (edge){b,lin[a]};lin[a] = edgenum;

	e[++edgenum] = (edge){a,lin[b]};lin[b] = edgenum;

	return;

}

double d[MAXN];

const double eps = 1e-8;

double val[MAXN];

int tot = 0;

double gete(int k)

{

	double maxv = 0,sumv = 0;

	tot = 0;

	for(int i = lin[k];i != 0;i = e[i].nxt)

	{

		val[++tot] = d[e[i].to];

		maxv = max(maxv,d[e[i].to]);

		sumv += d[e[i].to];

	}

	if((sumv + m) / deg[k] >= maxv)return (sumv + m) / deg[k];

	sort(val + 1,val + 1 + tot);

	double s = 0;

	int p;

	for(int i = 1;i < tot;++i)

	{

		s += val[i];p = i;

		if(s + m > val[i + 1] * (deg[k] - tot + i))continue;

		else break;

	}

	double l = val[p],r = val[p + 1],mid;

	while(r - l >= eps)

	{

		mid = (l + r) / 2;

		double sum = m;

		for(int i = lin[k];i != 0;i = e[i].nxt)

		{

			sum += min(mid,d[e[i].to]);

		}

		sum /= deg[k];

		if(sum >= mid)l = mid;

		else r = mid;

	}//cout << r << endl;

	return r;

}

bool inq[MAXN];

int main()

{

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

	int a,b;

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

	{

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

		add(a,b);

	}

	for(int i = 1;i <= n;++i)d[i] = 10000000000;

	d[n] = 0;

	priority_queue< pair<int,int> > q;q.push(make_pair(0,n));

	while(!q.empty())

	{

		int k = q.top().second;q.pop();

		if(inq[k])continue;

		inq[k] = true;

		for(int i = lin[k];i != 0;i = e[i].nxt)

		{

			double E;

			if(d[e[i].to] > d[k] && d[e[i].to] > (E = gete(e[i].to)))

			{

				d[e[i].to] = E;

				q.push(make_pair(-d[e[i].to],e[i].to));

			}

		}

	}

	printf("%.7lf\n",d[1]);

	return 0;

}